Not an answer. I would like to discuss some equivalent problems.
Let $\mathbb{S}^n_{\succeq 0}$ denote the set of $n\times n$ real symmetric positive semi-definite matrices.
We have
\begin{align}
&\|(A+C)^{1/2} - (B+C)^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \quad \forall A, B, C \in \mathbb{S}^n_{\succeq 0} \tag{1}\\
\Leftrightarrow \quad &\|(A+uu^T)^{1/2} - (B+uu^T)^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \quad \forall A, B\in \mathbb{S}^n_{\succeq 0}, \quad \forall u\in \mathbb{R}^n\tag{2}\\
\Leftrightarrow \quad
&\|(A+\mathrm{diag}(u^Tu, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(u^Tu, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|, \\
&\qquad \forall A, B\in \mathbb{S}^n_{\succeq 0}, \quad \forall u\in \mathbb{R}^n\tag{3}\\
\Leftrightarrow \quad
&\|(A+\mathrm{diag}(1, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(1, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|,\\
& \qquad \forall A, B\in \mathbb{S}^n_{\succeq 0}.\tag{4}
\end{align}
Thus, it suffices to prove that
$$\|(A+\mathrm{diag}(1, 0, \cdots, 0))^{1/2} - (B+\mathrm{diag}(1, 0, \cdots, 0))^{1/2}\| \le \|A^{1/2} - B^{1/2}\|.$$
Proof 1. In general, if $A$ and $B$ are two rectangular matrix such that $AB$ is a square matrix, then $\sigma_i(AB)\le\sigma_i(A)\sigma_1(B)$. Now put $A=X^{1/2}$ and $P=\Pi$, we obtain
\begin{aligned}
\operatorname{tr}\left((\Pi X\Pi)^{1/2}\right)
&=\operatorname{tr}\left(\left((X^{1/2}\Pi)^T (X^{1/2}\Pi)\right)^{1/2}\right)\\
&=\sum_i\sigma_i\left(X^{1/2}\Pi\right)\\
&\le\sum_i\sigma_i\left(X^{1/2}\right)\sigma_1(\Pi)\\
&\le\sum_i\sigma_i\left(X^{1/2}\right)
=\operatorname{tr}(X^{1/2}).
\end{aligned}
Proof 2. By a continuity argument and by a change of orthonormal basis, we may assume that $\Pi$ is a positive diagonal matrix. Let $Y=\Pi^{-1}(\Pi X\Pi)^{1/2}\Pi^{-1}$ and $A=Y\,\Pi$. Then
\begin{aligned}
X&=Y\,\Pi^2Y=AA^T,\\
(\Pi X\Pi)^{1/2}&=\Pi\,Y\,\Pi=\Pi\,A.
\end{aligned}
Note that $A=Y\,\Pi$ has a nonnegative diagonal because $Y$ is positive semidefinite and $\Pi$ is a positive diagonal matrix. Therefore $\operatorname{tr}(A)\ge\operatorname{tr}(\Pi\,A)$ and in turn,
$$
\operatorname{tr}(X^{1/2})
=\operatorname{tr}\left((AA^T)^{1/2}\right)
=\sum_i\sigma_i(A)
\ge\operatorname{tr}(A)
\ge\operatorname{tr}(\Pi\,A)
=\operatorname{tr}\left((\Pi X\Pi)^{1/2}\right).
$$
Best Answer
Yes, it's true. Assume first that $A,B$ are invertible (that is, positive definite). Then \begin{align} \text {Tr}((A+B)^{1/2}) &=\text{Tr}\,((A+B)^{-1/4}(A+B)(A+B)^{-1/4})\\ \ \\ &=\text{Tr}\,((A+B)^{-1/4}A(A+B)^{-1/4})+\text{Tr}\,((A+B)^{-1/4}B(A+B)^{-1/4})\\ \ \\ &=\text{Tr}\,(A^{1/2}(A+B)^{-1/2}A^{1/2})+\text{Tr}\,(B^{1/2}(A+B)^{-1/2}B^{1/2})\\ \ \\ &\leq\text{Tr}\,(A^{1/2})+\text{Tr}\,(B^{1/2}). \end{align} The inequality is justified by the fact that $A\leq A+B$ and the square root is monotone, so $A^{1/2}\leq (A+B)^{1/2}$. This (nontrivially ) implies that $$ (A+B)^{-1/2}\leq A^{-1/2}. $$Now conjugating with $A^{1/2}$, we get $$ A^{1/2}(A+B)^{-1/2}A^{1/2}\leq A^{1/2}. $$
For the general case we get by above that, for every $\varepsilon>0$, $$ \text{Tr}\,((A+B+\varepsilon I)^{1/2})\leq\text{Tr}\,((A+\varepsilon I)^{1/2})+\text{Tr}\,((B+\varepsilon I)^{1/2}). $$ The inequality then follows by making $\varepsilon\to0$. The trace is continuous, and $(A+\varepsilon I)^{1/2}-A^{1/2}=f_\varepsilon(A)$, where $f_\varepsilon(t)=(t+\varepsilon)^{1/2}-t^{1/2}$. Note that $$ |f_\varepsilon(t)|=\frac\varepsilon{(t+\varepsilon)^{1/2}+t^{1/2}}, $$ so $$\|(A+\varepsilon I)^{1/2}-A^{1/2}\|\leq\frac{\varepsilon}{(\lambda_m+\varepsilon)^{1/2}+\lambda_m^{1/2}}\leq\frac\varepsilon{2\lambda_m^{1/2}}, $$ where $\lambda_m$ is the smallest nonzero eigenvalue of $A$.