Thanks to Fedor Petrov for repeatedly pointing out my silly mistakes, and for suggestions how to improve the text (now I've rewritten the whole text).
$\let\eps\varepsilon\def\tr{\mathop{\rm tr}}\def\pr{\mathop{\rm pr}\nolimits}$
Denote $U_m=\sum_{i=1}^m u_iu_i^T$ ($U_m$ is regarded as a nonnegative self-agjoint operator in the Euclidean space). Set $f_m(x)=\langle U_mx,x\rangle=\sum_{i=1}^m\langle u_mx,u_mx\rangle^2$. By $\tr f$ we always mean the trace of the self-adjoint operator corresponding to a quadratic form $f$. Notice that $\tr f_m=\sum_{i=1}^m\|u_i\|^2$ and, more generally, $\tr f\big|_V=\sum_{i=1}^m\|\pr_Vu_i\|^2$ for every subspace $V$.
Let $\lambda_{1,m}\leq\dots\leq\lambda_{n,m}$ be the eigenvalues of $U_m$. Notice that
$$
\lambda_{i,m}=\max_{V_{n-i+1}}\min_{0\neq x\in V_{n-i+1}}f_m(x)/\|x\|^2
=\min_{V_{i}}\max_{0\neq x\in V_{i}}f_m(x)/\|x\|^2,
\qquad(*)
$$
where $V_j$ is assumed to run over all $j$-dimensional subspaces. Since $f_m(x)$ does not decrease as $m$ grows, we have $\lambda_{i,m+1}\geq \lambda_{i,m}$ for all $m$. Moreover, $\lambda_{1,m}\geq c>0$ for sufficiently large $m$ (and some constant $c$), and we consider only much larger values of $m$. Finally, notice that for every $V_j$ we have
$$
\lambda_{1,m}+\dots+\lambda_{j,m}\leq \tr f_m\big|_{V_j}
\leq \lambda_{n-j+1,m}+\dots+\lambda_{n,m}.
$$
Assume that the claim does not hold. We first show that $\lambda_{1,m}$ is bounded, and then show why it is impossible.
1. Assume that $\|U_m^{-1}u_m\|\geq \eps$ for some $m$. Set $v=U_m^{-1}u_m$, $w=U_{m-1}v$, $\alpha=\langle v,w\rangle=f_{m-1}(v)\geq \lambda_{1,m-1}\|v\|$ (so $\alpha$ is bounded away from $0$). Then $u_m=U_mv=w+\langle v,u_m\rangle u_m$ is collinear with $w$, $u_m=\beta w$. Now we have $\beta w=w+\beta^2\alpha w$, so $\alpha\beta^2-\beta+1=0$, $\beta=(1\pm\sqrt{1-4\alpha})/2\alpha$. This means that $\lambda_{1,m}\leq \alpha\leq 1/4$. So $\lambda_{1,m}\leq 1/4$ always. Moreover, $\beta$ is bounded away from $0$, as well as bounded from above (since $\alpha$ is not very small). Thus $f_m(v)=\langle v,w\rangle+\langle v,u_m\rangle^2=\alpha+(\beta\alpha)^2$ is also bounded by some constant $C_1$.
2.
Let $e_1,\dots,e_n$ be the orthonormal base in which $U_m$ diagonalizes as $\mathop{\rm diag}(\lambda_{1,m},\dots,\lambda_{n,m})$. Consider the expansion of $v$ in this base. Since $\|v\|\geq \eps$ and $f_{m}(v)\leq C_1$, some eigenvector $e_i$ with eigenvalue $\lambda_{i,m}\leq 2C_1/\eps=:C$ appears in this expansion with a coefficient $\mu$ which is bounded away from $0$. Then $\langle e_i,u_m\rangle=\mu\lambda_{i,m}$ is also bounded away from $0$ by some $\delta>0$.
Set $V_i$ to be the span of $e_1,\dots,e_i$. Then
$$
\lambda_{1,m}+\dots+\lambda_{i,m}
=\tr f_m\big|_{V_i}=\tr f_{m-1}\big|_{V_i}+\|\pr_{V_i}u_m\|^2
\geq \lambda_{1,m-1}+\dots+\lambda_{i,m-1}+\delta^2.
$$
This means that there exists some $k$ such that $C\geq \lambda_{k,m}\geq \lambda_{k,m-1}+\delta^2/n$. But such event (a small eigenvalue increases by at least $\delta^2/n$) may happen only finitely many times --- a contradiction.
