Froebenius norm is unitarily invariant.

Since $$ UA=[UA_1\ UA_2\ \ldots\ UA_n] $$ you need to prove that $$ \|UA\|_F^2=\sum_{j=1}^n\|UA_j\|_2^2\stackrel{?}{=}\sum_{j=1}^n\|A_j\|_2^2=\|A\|_F^2. $$ It suffice to prove that $\|UA_j\|_2^2=\|A_j\|_2^2$.

P.S. For $AU$ use conjugation.

Quick and dirty:

$$\|UA\|_F^2 = \operatorname{Tr}((UA)^*(UA)) = \operatorname{Tr}(A^*U^*UA) = \operatorname{Tr}(A^*A) = \|A\|_F^2$$ and then since $U^*$ is also unitary $$\|AU\|_F^2 = \|(U^*A^*)^*\|_F^2 = \|U^*A^*\|_F^2 = \|A^*\|_F^2 = \|A\|_F^2$$

---

Alternative argument:

Note that $A^*A \ge 0$ so there exists an orthonormal basis $\{u_1, \ldots, u_n\}$ for $\mathbb{C}^n$ such that $A^*A u_i = \lambda_i u_i$ for some $\lambda \ge 0$.

We have $$\sum_{i=1}^n \|Au_i\|_2^2 = \sum_{i=1}^n \langle Au_i, Au_i\rangle = \sum_{i=1}^n \langle A^*Au_i, u_i\rangle = \sum_{i=1}^n \lambda_i =\operatorname{Tr}(A^*A) = \|A\|_F^2$$

because the trace is the sum of eigenvalues.

The interesting part is that the sum $\sum_{i=1}^n \|Au_i\|_2^2$ is actually independent of the choice of the orthonormal basis $\{u_1, \ldots, u_n\}$. Indeed, if $\{v_1, \ldots, v_n\}$ is some other orthonormal basis for $\mathbb{C}^n$, we have \begin{align} \sum_{i=1}^n \|Au_i\|_2^2 &= \sum_{i=1}^n \langle A^*Au_i, u_i\rangle\\ &= \sum_{i=1}^n \left\langle \sum_{j=1}^n\langle u_i,v_j\rangle A^*A v_j , \sum_{k=1}^n\langle u_i,v_k\rangle v_k\right\rangle\\ &= \sum_{j=1}^n \sum_{k=1}^n \left(\sum_{i=1}^n\langle u_i,v_j\rangle \langle v_k,u_i\rangle\right)\langle A^*A v_j,v_k\rangle\\ &= \sum_{j=1}^n \sum_{k=1}^n \langle v_j,v_k\rangle\langle A^*A v_j,v_k\rangle\\ &= \sum_{j=1}^n \langle A^*A v_j,v_j\rangle\\ &= \sum_{j=1}^n \|Av_j\|_2^2 \end{align}

Now, if $U$ is unitary, for any orthonormal basis $\{u_1, \ldots, u_n\}$ we have that $\{Uu_1, \ldots, Uu_n\}$ is also an orthonormal basis so:

$$\|AU\|_F^2 = \sum_{i=1}^n \|A(Ue_i)\|^2 = \|A\|_F^2$$