In general the Frobenius and nuclear norm are not a good proxy for rank. The norms depend on the singular values $||X||_* = \sum_i \sigma_i(X)$ and $||X||_F^2 = \sum_i \sigma_i^2(X)$... so if the singular values of your matrix are all too small or too large, then you have a bad approximation to the rank.
However, you are right that when the singular values are clustered somewhere near one both norms can give a good approximation of the rank. Lets look at a bound...
If the $r$ nonzero singular values $\sigma_1,...,\sigma_r$ of a rank $r$ matrix $X$ are bounded by $|1-\sigma_i| \leq \epsilon/r$ for a error tolerance $0\leq\epsilon<r$, then $|r - ||X||_*| \leq \epsilon$. This bound tells us that as the your error in the approximation of the rank grows, the singular values can correspondingly grow linearly.
For the Frobenius norm: If the $r$ nonzero singular values $\sigma_1,...,\sigma_r$ of a rank $r$ matrix $X$ are bounded by $\sqrt{1-\epsilon/r}\leq\sigma_i\leq\sqrt{1+\epsilon/r}$, then $|r - ||X||_*| \leq \epsilon$. In this case if we increase our approximation error tolerance, our singular values can only grow according to this square root function.
In other words, these bounds show that regardless of norm choice you don't have a lot of wiggle room in your singular values if you want your norm to well approximate rank. However, for the nuclear norm you have more wiggle room than Frobenius.
A good rule of thumb is that the nuclear norm can achieve the same approximation to rank as the Frobenius rule with about twice as much freedom in singular values(interval twice as large), and that the singular values should always be near one.
In your minimization problem, it is hard to know how to constrain $X$ to ensure well approximation of the rank. Perhaps normalizing the spectral radius of $A$ and $B$ could help, or constraining $X$ with the spectral norm $||Ax||/||x||$.
This is a simple consequence of Cauchy-Schwarz inequality. Let $X=PSQ'$ be a singular value decomposition of $X$. If $UV'=X$, then
$$
\|X\|_\sigma
=\operatorname{tr}(S)
=\operatorname{tr}(P'UV'Q)
\le\|P'U\|_F\|Q'V\|_F
=\|U\|_F\|V\|_F
\le\frac12(\|U\|_F^2+\|V\|_F^2).
$$
Since ties occur when $U=PS^{1/2}$ and $V=QS^{1/2}$, the conclusion follows.
Best Answer
For convenience, let $|M| = \sqrt{M^*M}$.
It suffices to note that $$ \langle A,B \rangle = \operatorname{Tr}(AB^*) = \operatorname{Tr}(B^*A) $$ is an inner product on the space of $m \times n$ matrices. From there, the properties of an inner product are enough to prove the Cauchy-Schwarz inequality: $$ |\operatorname{Tr}(AB^*)| = |\langle A,B \rangle| \leq \|A\| \cdot \|B\| \ = \sqrt{\operatorname{Tr}(A^*A)\operatorname{Tr}(B^*B)} = \sqrt{\operatorname{Tr}(|A|^2) \operatorname{Tr}(|B|^2)} $$ Now, if $M$ has rank $r$, then the polar decomposition tells us that there exists a partial isometry $U$ (i.e. $U^*U$ is an orthogonal projection) with $\operatorname{rank}(U) = M$ such that $M = U|M|$ and $|M| = U^*M$. From there, $$ \operatorname{Tr}(|M|)^2 = \langle M,U \rangle^2 \leq \langle M, M \rangle \langle U,U \rangle = \operatorname{Tr}(M^*M) \cdot \operatorname{rank}(M) $$