As Will noted, you will have to have $n$ even for there to be any solutions. (This holds even if the $a_{ij}$ are allowed to be formal power series in the $x_i$, since ${x_1}^2+\cdots+{x_n}^2$ is not a square even in this larger ring.)
One special case deserves mention because we do know all the dimensions in which there exist solutions in this case: Assume that $A(x)$ has no constant term, i.e., $A(0)=0_n$. Then your question comes down to a question about Clifford algebras: Write $A = A^i\,x_i + R_2(x)$ where $R_2(x)$ vanishes to order $2$ in $x$ and the $A^i$ are $n$-by-$n$ matrices. Then the equation $A^2=M = ({x_1}^2+\cdots+{x_n}^2)I_n$ implies, in particular, that $A^iA^j+A^jA^i = 2\delta^{ij}I_n$. These are the defining equations of a Clifford algebra over $\mathbb{F}$.
For simplicity, take $\mathbb{F}=\mathbb{C}$. The algebra $\mathbb{C}\ell_n$ generated over $\mathbb{C}$ by $n$ generators $J^i$ subject only to to the relations $J^iJ^j+J^jJ^i = 2\delta^{ij} 1$, is known to have dimension $2^n$ and, since $n$ is even, it is also known to be isomorphic to $M_N(\mathbb{C})$, the algebra of $N$-by-$N$ matrices with complex entries, where $N = 2^{n/2}$. (See any book on Clifford algebras.)
The assignment $J^i\mapsto A^i$ induces a homomorphism $a:\mathbb{C}\ell_n (= M_N(\mathbb{C}))\to M_n(\mathbb{C})$ of algebras with unit, and, by the usual theory of matrix algebras, this can only happen if $N$ divides $n$, i.e., if $2^{n/2}$ divides $n$. Of course, this only holds when $n=2$ and $n=4$.
Conversely, if $n=2$ or $n=4$, then $\mathbb{C}\ell_n$ is isomorphic to $M_n(\mathbb{C})$, so the desired $A^i$ do exist satisfying $A^iA^j+A^jA^i = 2\delta^{ij}I_n$ (and they are unique up to conjugation), and we can simply take $A = A^i\,x_i$ (i.e., $R_2(x)=0$) to get a solution.
Obviously, if a solution of this kind existed with $\mathbb{F}= \mathbb{Q}$ or $\mathbb{R}$, then, we could complexify and get a solution with $\mathbb{F}=\mathbb{C}$, so the only dimensions in which solutions of this kind exist are when $n=2$ or $n=4$.
Finally, when $n=2m$, there is always a nontrivial solution with $A(0)\not=0_n$, just take $$ A = \begin{pmatrix}0_m & I_m \\ ({x_1}^2+\cdots+{x_n}^2)I_m & 0_m\end{pmatrix}. $$