Let $f(n)$ and $g(n)$ be two increasing functions of $n$ such that:
$$ f \leq g + O(\sqrt{g}) + O(\sqrt{f}) $$
Is it true that:
$$ f \leq g + O(\sqrt{g}) $$
? If not, then what would be a good asymptotic upper bound on $f$?
NOTE: the asymptotic behavior is when $n\to\infty$.
This does not hold; for instance, take the following, where the asymptotics are taken around $+\infty$: $$ f(x) = \frac{1}{x}, \qquad g(x)=\frac{1}{x^3} $$ Then $$f(x) = \frac{1}{x} \leq \frac{1}{x^3} + O(x^{-3/2}) + O(x^{-1/2}) = O(x^{-1/2}) = O(\sqrt{f(x)})$$ but we do not have $f(x) \leq x^{-3} + O(x^{-3/2}) = O(x^{-3/2})$. You can adapt this example to other situations: you cannot get a better bound only in terms of $g$, since if the "relevant" upper bound from the first line if $f=O(\sqrt{f})$ then $g$ and $f$ can be arbitrarily unrelated.
Following the clarification from the OP: Now, assuming further that $f\nearrow \infty$ and $g$ is non-decreasing: $\sqrt{f} = o(f)$, so that we must have $f \leq g + O(\sqrt{g})$. Indeed, dividing by $\sqrt{f}$, we get $$ \sqrt{f} \leq \frac{g}{\sqrt{f}} + O\left(\sqrt{\frac{g}{f}}\right) + O(1) $$ and since the LHS goes to infinity, so does the RHS. this implies in turn that $\sqrt{g}=o(g)$: otherwise, we do not have $g\to\infty$, so by monotonicity $g$ converges to a finite limit, and thus so does $\sqrt{g}$: the RHS does not go to infinity.
It follows that $\sqrt{g}=o(g)$, and therefore $g\nearrow\infty$; and we also get that $g = \Omega(f)$. Indeed, otherwise we would have $g=o(f)$ (not quite, but for a subsequence at least -- ignoring this detail), so that we would get, from the beginning: $$ f \leq o(f) + O(\sqrt{f}) = o(f) $$ which is impossible. Finally, this means that $\sqrt{g} = \Omega(\sqrt{f})$, and therefore $$ f \leq g + O(\sqrt{g}). $$