Contrary to my first impression, this question is answered completely and thoroughly by G.A. Watson in Characterization of the Subdifferential of Some Matrix Norms. For the final derivation, see pg. 40.
The conclusion is that
$$\partial \|K\|_* = \left\{ UV^T+W:\ \ \ \|W\|<1, \text{columnspace}(U) \perp W\perp\text{ rowspace(V)} \right\},$$
where $\|\cdot\|$ is the spectral norm, which is dual to the nuclear norm.
It is sufficient to prove that the nuclear norm is, in fact, a norm. It's trivial to verify that $\|A\|=0$ only if $A=0$, and that $\|tA\|=|t|\|A\|$ if $t$ is a scalar. The one non-trivial requirement is that the norm satisfies the triangle inequality; that is,
$$\|A+B\|\leq \|A\|+\|B\|.$$
To do that, we're going to prove this:
$$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle =
\sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(Q^HA) = \sum_i \sigma_i(A) = \|A\|.$$
Since $\sigma_1(\cdot)$ is itself a norm, what we're actually proving here is that the nuclear norm is dual to the spectral norm.
Let $A=U\Sigma V^H=\sum_i \sigma_i u_i v_i^H$ be the singular value decomposition of $A$, and define $Q=UV^H=UIV^H$. Then $\sigma_1(Q)=1$ by construction, and
$$\langle Q, A \rangle = \langle UV^H, U\Sigma V^H \rangle = \mathop{\textrm{Tr}}(VU^HU\Sigma V^H)
= \mathop{\textrm{Tr}}(V^HVU^HU\Sigma) = \mathop{\textrm{Tr}}(\Sigma) = \sum_i \sigma_i.$$
(Note our use of the identity $\mathop{\textrm{Tr}}(ABC)=\mathop{\textrm{Tr}}(CAB)$; this is always true when both multiplications are well-posed.)
So we have established that
$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle \geq \sum_i \sigma_i(A)$.
Now let's prove the other direction:
$$\sup_{\sigma_1(Q)\leq 1} \langle Q, A \rangle =
\sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(Q^HU\Sigma V^H) =
\sup_{\sigma_1(Q)\leq 1} \mathop{\textrm{Tr}}(V^HQ^HU\Sigma) =
\sup_{\sigma_1(Q)\leq 1} \langle U^HQV, \Sigma \rangle =
\sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i (U^HQV)_{ii} =
\sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i u_i^H Q v_i \leq
\sup_{\sigma_1(Q)\leq 1} \sum_{i=1}^n \sigma_i \sigma_\max(Q) =
\sum_{i=1}^n \sigma_i.
$$
We have proven both the $\leq$ and $\geq$ cases, so equality is confirmed.
Why did we go through all of this trouble? To make proving the triangle inequality easy:
$$\|A+B\|=\sup_{V:\sigma_\max(V)\leq 1} \langle V, A+B \rangle
\leq \sup_{V:\sigma_\max(V)\leq 1} \langle V, A \rangle +
\sup_{V:\sigma_\max(V)\leq 1} \langle V, B\rangle = \|A\| + \|B\|.$$
Best Answer
Hint: Let $|M| = \sqrt{M^TM}$. Note that $|A|^2$ and $|B|^2$ commute with $|A|^2\;|B|^2 = 0$. Since there exist polynomials $p,q$ with $|A| = p(A^TA)$ and $|B| = q(B^TB)$, we can conclude that $|A|,|B|$ commute with $|A| \, |B| = 0$. So, we have $$ (|A| + |B|)^2 = |A|^2 + |B|^2 = A^TA + B^TB = |A + B|^2. $$ So, $|A+B| = |A| + |B|$.