Frobenius Norm and Relation to Eigenvalues

You are in the right way. The corresponding Schur decomposition is $A = Q U Q^*$, where $Q$ is unitary and $U$ is an upper triangular matrix, whose diagonal corresponds to the set of eigenvalues of $A$ (because $A$ and $U$ are similar). Now because Frobenius norm is invariant under unitary matrix multiplication:

$$||QA||_F = sqrt{text{tr}((QA)^*(QA))} = sqrt{text{tr}(A^*Q^* QA)} = sqrt{text{tr}(A^*A)} = ||A||_F$$

(the same remains for multiplication of $Q$ on the right) then we could write: $$||A||_F = ||Q U Q^*||_F = ||U||_F rightarrow sqrt{sum_{j=1}^n |lambda_j|^2} leq ||A||_F$$

directly proves your statement.

Note: The inequality comes from the definition of the Frobenius norm: The sum of the square of all entries in the matrix. Since $U$ contains the eigenvalues on his diagonal, the term in the left has to be less or equal to the sum over all entries, because $U$ could have non zero entries over his diagonal.