Per refguide page for Solve:
"Solve gives generic solutions only. Solutions that are valid only when continuous parameters satisfy equations are removed. Other solutions that are only conditionally valid are expressed as ConditionalExpression objects."
This system imposes nongeneric conditions, specifically on the parameters {x,y}. So you might instead also solve for one of them, I guess x since you appear to want solutions not in terms of x, so leaving y to act as a symbolic parameter will have this effect.
Solve[y == x^2 && a == x, {a, x}]
(* Out[97]= {{a -> -Sqrt[y], x -> -Sqrt[y]}, {a -> Sqrt[y], x -> Sqrt[y]}} *)
Alternatively there is the undocumented allowing of the third variable to represent variables to eliminate. As this comprises a conflict with the intended and documented third argument (as a domain of interest), there is a warning message.
Solve[y == x^2 && a == x, a, x]
(* During evaluation of In[96]:= Solve::bdomv: Warning: x is not a valid domain specification. Assuming it is a variable to eliminate.
Out[96]= {{a -> -Sqrt[y]}, {a -> Sqrt[y]}} *)
Also of relevance is the MaxExtraConditions option, as this allows one to find nongeneric solutions that lie in a space no smaller than a given codimension (it will return conditions that specify said space).
Solve[y == x^2 && a == x, a, MaxExtraConditions -> 1]
(* Out[98]= {{a -> ConditionalExpression[x, x^2 - y == 0]}} *)
This has the limitation that one cannot specify how to "order" the parameters {x,y} and, in particular, we get a perfectly correct solution that is not give a as an explicit function of y.
