As Will notes, this does not really work for odd $n \gt 1$ as the determinant of $M$ is not a square. On the other hand, if $n$ is even then the determinant of $M$ is a square. 

Note that your solution to $A^2=M$ for $n=2$ has $A$ symmetric and thus is also a solution of $AA^t=M$. I think $AA^t=M$ is the more promising equation to generalize. 

In either version, when $n=2m$, the determinant of $A$ would have to be $(x_1^2+x_2^2+\cdots +x_n^2)^m.$ It is hard to imagine this happening without the entries of $A$ all being of the form $\pm x_i.$ That is the only case I will consider.


I don't think there is a solution to $A^2=M$ for $n=4.$ However, $$A=\begin{pmatrix}
x_1 & x_2 &x_3 &x_4\\
x_2 & -x_1 &x_4 & -x_3 \\
x_4 &x_3&-x_2&-x_1\\
x_3&-x_4&-x_1&x_2
\end{pmatrix}$$
does give $AA^t=M.$



If all the $x_i$ are set equal to $1$ then $A$ would become a matrix with entries $\pm 1$ such that $A^2=nI_n$ or $AA^t=nI_n$, depending on which version one is trying to solve. In the $AA^t$ case one would have a Hadamard matrix which means that $n=1,2$ or a multiple of $4.$

I suppose having enties of the form $\zeta x_i$ with $\zeta$ a root of unity could also be worth considering.