Let us first solve the equation $\mathbf{M}\mathbf{y}=\mathbf{0}$. The simplest way to do so is to prepend an extra row $(1,1,\dots,1)$ to $\mathbf{M}$, resulting in a (transposed) Vandermonde matrix $\mathbf{M'}$. Then the equation $\mathbf{M}\mathbf{y}=\mathbf{0}$ corresponds to the equation $$(\star)\qquad\mathbf{M'}\mathbf{y}=(s,0,0,\dots,0)^T,$$ where $s=y_1+\dots+y_n$ is a parameter.
Solution $(\star)$ can be easily obtained by Cramer's rule and the formula for Vandermonde determinant. Namely, let $V(\alpha_1,\dots,\alpha_k)$ be the determinant of the Vandermonde matrix formed by powers of $\alpha_1,\dots,\alpha_k$, then for every $i=1,2,\dots,n$ we have $$y_i = s\cdot(-1)^{i-1}\cdot \left(\frac{n!}{i}\right)^{2(n-1)} \cdot\frac{V(1^2,2^2,\dots,(i-1)^2,(i+1)^2,\dots,n^2)}{V(1^2,2^2,\dots,n^2)}.$$
By the definition of $s$, we also have $\sum_{i=0}^n x_i^2 = 1 -2 \sum_{i=1}^n y_i = 1-2s$.
Now, we need to solve the equation $$(\star\star)\qquad\left(\begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_n \end{array}\right)= \left(\begin{array}{cc} x_1 & x_2 & \cdots & x_{n-1} & x_n\\ x_2 & x_3 & \cdots & x_n & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots\\ x_n & 0 & \cdots & 0 & 0 \end{array}\right) \left(\begin{array}{c} 1 \\ x_1 \\ \vdots \\ x_{n-1} \end{array}\right)$$ with respect to $x_1,\dots,x_n$.
Let us define the generating function: $$X(t) = 1 + x_1 t + x_2t^2 \dots + x_n t^n.$$ Then the equation $(\star\star)$ is equivalent to the following identity for polynomials in $t$: $$X(t)\cdot X(t^{-1}) = 1-2s + y_{1}(t+t^{-1}) + y_{2}(t^2+t^{-2}) + \dots + y_n(t^n+t^{-n}).$$
The $2n$ (complex) zeros of the r.h.s. here (which can be turned into a polynomial of degree $2n$ by multiplying by $t^n$, or by representing it as a polynomial of degree $n$ in $t+t^{-1}$) come in pairs $\{t_k,t_k^{-1}\}$, $k=1,\dots,n$. Picking one zero from each pair, we can construct a polynomial $X(t)$ of degree $n$ that has these $n$ zeros and obtain $x_i$ as its coefficients. So, in general one can get $2^n$ different solutions for $(\star\star)$.