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.