I have two equations: $x^2 - y = 0$ and $y^2 - x = 0$. Adding them gives $x^2 - x + y^2 - y = 0$, and completing the square results in $(x - 1/2)^2 + (y-1/2)^2 = 1/2$. This suggests that there is an infinite number of solutions on the circle centered at (1/2, 1/2) with a radius of 1/4. However, only the solutions 0 and 1 actually work in the original equations.
I understand that the original equations result in $y = x^2$, and, substituting this into the other equation, $x(x^3 - 1) = 0$, which provides the solutions 0 and 1, but why don't all points on the circle defined above work as solutions in these equations since, after all, the circle was derived from those equations?
Your logical steps are
$(x^2 - y = 0) \wedge (y^2 - x = 0) \implies (x^2-x+y^2-y=0)$. The implication doesn't go the ohter way around.
The core of it is that if $A=0$ and $B=0$, then $A+B=0$. But if $A+B=0$ then we can't say that $A=0$ and $B=0$, because it's possible for example that $A=5$ and $B=-5$.
Sometimes we gloss over $x$ and $y$ as formal symbols, but in situations like these I always like to think of $x$ and $y$ as actual concrete numbers. Imagine that you have two concrete numbers $x$ and $y$, and if you compute $x^2-y$ and $y^2-x$ you get $0$ each time. Then for sure if you compute $(x^2-y)+(y^2-x)$ you will get $0$ also. But now imagine you have two concrete numbers (maybe different, maybe not; but I will still call them $x, y$) such that when you compute $(x^2-y)+(y^2-x)$ you get zero. But this does not mean for sure that if you compute $x^2-y$ and $y^2-x$ you will get zero for them (though if you get $0$ for one, you will for sure get $0$ for the other). You can find such examples by simply taking a point on the circle you describe which does not satisfy the two smaller equations.