That is not from a proof of the existence of the real numbers. That is stated much later in the chapter and the proof is in an appendix if memory serves me right.
Note that this is "just" a proof that $\mathbb Q$ is not Dedekind complete by exhibiting something kind of like a Dedekind cut $(A,B)$ (except only with positive rationals) where $A$ doesn't have a supremum (in $\mathbb Q$) and $B$ doesn't have an infimum (in $\mathbb Q$).
While the proof of this fact is perfectly correct and clear, it does suffer from the slight blemish that his formula for $q$ seems to be pulled out of thin air.
In response to your comment: It's a standard exercise in real analysis to prove that when $a>0$ then the recursively defined sequence $\bigl(\tfrac12(x_n + \frac{a}{x_n})\bigr)_{n\geq1}$ converges monotonically to $\sqrt a$ for any choice of $x_1>\sqrt a$ (this is the Babylonian method for computing square roots). Using this, you could instead define $q = \tfrac12(p + \frac2p)$ for $p>\sqrt2$.
Rudin's idea is based on something similar: make $q$ a better approximation to $\sqrt2$ than $p$ without accidentally getting to the other side of $\sqrt2$. That's what subtracting $\frac{p^2-2}{p+2}$ from $p$ does. It's just enough to get closer, but not enough to overshoot.