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][1] $\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][2] 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)$.

  [1]: https://en.wikipedia.org/wiki/Vandermonde_matrix
  [2]: https://en.wikipedia.org/wiki/Cramer%27s_rule