Write $A+uv^T=A(I+A^{-1}uv^T)$; we are to find an inverse of $I+A^{-1}uv^T$. It's a bit simpler if we set $w=-u$, so instead we look for an inverse of $I-A^{-1}wv^T$; the idea that comes to mind is to consider, formally,
$$
(I-A^{-1}wv^T)^{-1}=I+A^{-1}wv^T+(A^{-1}wv^T)^2+(A^{-1}wv^T)^3+\dotsb \tag{*}
$$
taking from $\frac{1}{1-x}=1+x+x^2+\dotsb$
Now
$$
(A^{-1}wv^T)^2=A^{-1}wv^TA^{-1}wv^T=(v^TA^{-1}w)A^{-1}wv^T
$$
and
$$
(A^{-1}wv^T)^3=
A^{-1}wv^TA^{-1}wv^TA^{-1}wv^TA^{-1}wv^T=
(v^TA^{-1}w)^2A^{-1}wv^T
$$
and, by induction,
$$
(A^{-1}wv^T)^n=(v^TA^{-1}w)^{n-1}A^{-1}wv^T
$$
so the formal sum (*) becomes
$$
I+A^{-1}wv^T+(v^TA^{-1}w)A^{-1}wv^T+(v^TA^{-1}w)^2A^{-1}wv^T+(v^TA^{-1}w)^3A^{-1}wv^T+\dotsb
$$
and therefore
$$
I+\biggl(\,\sum_{n\ge0}(v^TA^{-1}w)^n\biggr)A^{-1}wv^T
$$
The term in parentheses is the inverse of $1-v^TA^{-1}w$. Returning to $u$, we find that the inverse should be
$$
I-\frac{1}{1+v^TA^{-1}u}A^{-1}uv^T
$$
Multiplying on the right by $A^{-1}$ we see that the inverse of $A+uv^T$ should be
$$
A^{-1}-\frac{1}{1+v^TA^{-1}u}A^{-1}uv^TA^{-1}
$$
Now we can do the multiplication and verify that the intuition is correct.