We will actually prove something stronger and then see that the desired result follows.
Let $A$ be defined as in the problem and take $\newcommand{\Atr}{A^{\dagger}}B = \Atr A$. Let $a_{ij}$ denote the $(i,j)$th element of $A$. Note that the diagonal elements of $B$, which we denote by $b_{ii}$ are real nonnegative numbers. We assume without loss of generality that $b_{ii} \geq b_{i+1,i+1} \geq 0$ for all $1 \leq i < n$.
Claim 1: The diagonal of $B$ majorizes $(|a_{ij}|^2)_{ij}$.
Let $s_k = \sum_{i=1}^k b_{ii}$ denote the sum of the $k$ largest $b_{ii}$. For each $i$, $b_{ii} = \sum_{j=1}^n |a_{ji}|^2$ is the sum of the squared moduli of the elements in the $i$th column of $A$. Consider the $k$ largest $|a_{ij}|^2$. Then, these $k$ elements lie within no more than $k$ unique columns of $A$ and, so, the sum of these $k$ elements is clearly less than or equal to the sum of the corresponding $b_{ii}$'s. But, this latter sum is definitely smaller than $s_k$. This holds for each $1 \leq k \leq n$ and so the claim is established since also $\sum_{i=1}^n b_{ii} = \sum_{i=1}^n \sum_{j=1}^n |a_{ij}|^2$.
Theorem (von Neumann): Let $S$ and $T$ be arbitrary complex-valued $n \times n$ matrices. Let $(\sigma_i)$ and $(\tau_i)$ be the singular values of $S$ and $T$, respectively, in nonincreasing order. Then, $|\mathrm{Tr}(ST)| \leq \sum_{i=1}^n \sigma_i \tau_i$.
A nice, elementary proof of this can be found in
L. Mirsky, A trace inequality of John von Neumann, Monatsh. Math. 79 (4): 303–306, 1975, MR0371930.
We don't actually need such a strong statement to prove the next claim, but I give the result above because it's very nice and doesn't seem to be as well-known as it should be.
Claim 2: Let $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$ be the eigenvalues of $B$. Then $(\lambda_i)$ majorizes $(b_{ii})$.
$B$ has an eigendecomposition such that $B = Q \Lambda Q^*$ where $Q$ is unitary and $\Lambda$ is a diagonal matrix corresponding to $(\lambda_i)$. Now, note that $\newcommand{\Tr}{\mathrm{Tr}} s_k = \Tr(J_k^T B J_k) $ where $\newcommand{\zmat}{\mathbf{0}} J_k = \left(\begin{matrix} I_k \\ \zmat \end{matrix}\right) $ with $I_k$ being a $k \times k$ identity matrix and $\zmat$ being an $(n-k) \times k$ all-zeros matrix.
Then $ \Tr(J_k^T B J_k) = \Tr(J_k^T Q \Lambda Q^* J_k) = \Tr(Q^* J_k J_k^T Q \Lambda) \>. $
Observe that $Q^* J_k J_k^T Q$ is a Hermitian matrix with $k$ singular values that are one and $n-k$ that are 0, and so by von Neumann's theorem, we get that $ s_k = |s_k| = |\Tr(J_k^T B J_k)| \leq \sum_{i=1}^k 1 \cdot \lambda_i = \sum_{i=1}^k \lambda_i \> . $
Since this holds for each $k \leq n$, the claim is established.
Epilogue: Combining Claims 1 and 2 gives the desired result as stated in the question. But, Claim 2 by itself is actually quite a bit stronger. Also, as alluded to above, more elementary means can be used to show Claim 2 and they are almost as easy as wielding von Neumann's somewhat bigger hammer.