This answer is now complete: the only such $f$ are the constant $0$ and the constant $1$.
Things in block quotes will be true regardless of the assumptions made in the surrounding text.
As you point out,
If $f$ has a root, then $f(0) = 0$, and $f(x) \in \{0,1\}$ for all $x$, and $$f(x+f(y)) = f(x+y)$$
Clearly $f=0$ is a solution. Otherwise, suppose $f(y)=1$. Then for all $x$, $f(x+1) = f(x+y)$, so letting $x=1$ we have $f(y-1) = 0$. [Call this property DECREMENT.]
On the other hand, whenever $f(y) = 0$ we have $f(x) = f(x+y)$ for all $x$. Therefore $f(x) = f(x+yn)$ for all $x$ and for all $n \in \mathbb{Z}$. [Call this property TRANSLATE, and if $y$ is fixed with $f(y)=0$, let TRANSLATE(n) denote the fact that $f(x) = f(x+yn)$ for all $x$.]
So suppose $f(0) = f(1) = 0$, and $f(y) = 1$. Then $f(y-1) = 0$ (DECREMENT) but also $f(y-1) = f(y-1+1)$ (TRANSLATE(1)) which is $f(y) = 1$, a contradiction.
If $f(1) = 0$, then $f$ is the constant $0$ function.
So if $f(0) = 0$ but $f$ is nonzero, then $f(1) = 1$. Hence $f(2) = 0$ (since if not, it would be $1$ and hence we would have $f(2-1) = 0$ by DECREMENT), and so $f(x) = f(x+2n)$ for all $x$ and all $n \in \mathbb{Z}$. That is, $f$ is defined by its values on $(-1, 1]$.
Moreover, in that case $f\left(\frac{1}{n}\right) = 1$ for all $n>1$ because if $f\left(\frac{1}{n}\right) = 0$ then $0 = f(0) = f\left(0+\frac{1}{n} \times n \right)$ by TRANSLATE(n), which is $f(1) = 1$, a contradiction.
This means that $f\left(\frac{1}{n}-1\right) = 0$ for $n>1$, so for all $x \in \mathbb{R}, m \in \mathbb{Z}, n > 1$ we have $f(x) = f(x+m(\frac{1}{n}-1))$ by TRANSLATE(m); in particular, letting $x=m$ we have $f(m) = f(\frac{m}{n})$ for all $m \in \mathbb{Z}, n > 1$. So letting $m=3n$, we have $f(3) = f(3n)$ for all $n > 1$; but $f(3) = f(1) = 1$ by TRANSLATE(2) and so $f(3n) = 1$. Letting $n=2$, we obtain $f(6) = 1$, but we already know $f(2k) = 0$ for all $k$ by TRANSLATE(2), so we obtain a contradiction.
If $f$ has a root, then $f$ is the constant $0$ function.
(Actually I think @lulu's trick works to show this much faster.)
If ever $y = f(y)^2$, then $f(x+y) = f(x+y)^2$ for all $x$, so $f(x) \in \{0,1\}$ for all $x$.
So it has a root unless it's the constant $1$ function.
If $f$ is not the constant $1$ function, and there is some $y$ with $y=f(y)^2$, then $f$ is the constant $0$ function.
In particular,
If $f(1) = 1$, then $f$ is the constant $1$ function. $f(1)$ cannot be $-1$.
If $y$ is such that $f(y) = 1$, then $f(x+1) = f(x+y)^2$ for all $x$, so letting $x=y-1$ we obtain $1 = f(y) = f(1)^2$, so $f(1) = 1$ or $f(1) = -1$ (the latter being a contradiction). That is:
If $f$ ever hits $1$, then $f$ is the constant $1$ function.
Note that by letting $x=0$, we see that $f$ has a fixed point at $f(y)^2$ for every $y$.
So, letting $y=0$, we obtain $f(x+f(0)^2) = f(x)^2$, which means that $f(x+f(0)^2)$ is a fixed point of $f$ for every $x$.
In particular, letting $x=-f(0)^2+z$,
$f(z)$ is a fixed point of $f$ for every $z$. (That is, $f$ is idempotent: $y$ is a fixed point of $f$ iff $y$ is in the range of $f$.)
Also let $x = y-f(y)^2$ to obtain
$f(y) \geq 0$ for all $y$.
And let $x=0$ to obtain $f(f(y)^2) = f(y)^2$; that is, the square of anything in the range of $f$ is a fixed point of $f$, or
The square of a fixed point is a fixed point.
Now, let $x=f(y)^2$ and $y=0$ to obtain $$f(2a^2) = f(a^2)^2$$ where $a=f(0)$; so $f(2a^2) = a^4$ since the square of a fixed point $a$ is a fixed point $a^2$.
Let $x=\bar{x}, y=\bar{x}$ where $\bar{x}$ is a fixed point, to obtain $f(\bar{x} + f(\bar{x})^2) = f(2\bar{x})^2$, or $f(\bar{x} + \bar{x}^2) = f(2 \bar{x})^2$.
Let $x = \bar{x}^2, y=\bar{x}$ to obtain $f(\bar{x}^2+f(\bar{x})^2) = f(\bar{x}+\bar{x}^2)^2$.
Combining those facts, obtain:
If $\bar{x}$ is a fixed point of $f$, then $f(2\bar{x}^2) = f(2\bar{x})^4$.
And let $x=a^2, y=0$ to obtain $f(2a^2) = f(a^2)^2$, so $f(2a^2) = a^4$ since $a^2$ is a fixed point, so by the previous fact, $a^4 = f(2a)^4$; since $a=f(0)$ is in the range of $f$, and since $f$ is always positive, we have:
$a = f(2a)$.
Now, we prove by induction that $f(na) = a$.
Indeed, let $y=na$ and $x=a$.
Then $$f(a+f(na)^2) = f(a(n+1))^2$$ which by inductive hypothesis means $$f(a+a^2) = f(a(n+1))^2$$
But we already know that $f(a+a^2) = f(2a)^2$ because that's just the definition of $f$ with $x=a, y=a$; so $f(a(n+1))^2 = f(2a)^2$, which we already know is $a$.
So
$f(na) = a$ for every positive integer $n$.
Let $n = m a$ to obtain:
$f(ma^2) = a$ whenever $ma$ is integer.
In particular, let $a=\frac{p}{q}$, and let $m=q$, to obtain $f(qa^2) = a$.
But you have already shown that $f(ma^2) = a^{2^m}$ for every $m$, so we have $a = a^{2^q}$. That is, $a=0$ or $a=1$ (since $m \not = 0$); so $f$ hits $0$ or $1$.
