For which kinds of group $G$, can we identify a square element efficiently?

For a finite group $G$, there is a long-standing answer to this question using character theory. If $\chi$ is an irreducible complex character of $G$, then its Frobenius-Schur indicator $\nu(\chi)$ is defined by $\nu(\chi) = \frac{1}{|G|} \sum_{g \in G} \chi(g^{2}).$ It is known that $\nu(\chi) \in \{0,1,-1\},$ and that $\nu(\chi) = 0$ if $\chi$ is not real-valued,$\nu(\chi) = 1$ if $\chi$ is real-valued may be afforded by a representation over $\mathbb{R},$ while $\nu(\chi) = -1$ if $\chi$ is real-valued, but may not be afforded by any representation over $\mathbb{R}.$

It then follows from the orthogonality relations for group characters that for any $x \in G,$ the number of $g \in G$ such that $g^{2} = x$ is given by the formula $\sum_{\chi \in {\rm Irr}(G)} \nu(\chi)\chi(x)$, where ${\rm Irr}(G)$ is the set of complex irreducible characters of $G$. Note that $x$ is a square in $G$ if and only if this expression is non-zero.

To complete the picture, for an infinite finitely presented group, the answer can be "it is undecidable". That is, there exists a group $G$ given by a finite set of generators $X$ and a finite set of relations $R$ for which there is no algorithm to decide, given an element $g\in G$, if $g$ is a square in $G$. One example of such a group is Kharlampovich's group from MR0631441, Kharlampovich, O. G., A finitely presented solvable group with unsolvable word problem. Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 4, 852--873 (one needs to take $p=2$ in her construction). Indeed, if an element belongs to the center of Kharlampovich's group with $p=2$, then it is a square in the group if and only if it is equal to 1, and Kharlampovich proved that this property is undecidable.

You can decide whether a given element in a torsion-free hyperbolic group is a square. This class includes finitely generated free groups, torsion-free groups acting (nicely) on trees, and fundamental groups of closed surfaces with negative Euler characteristic.

Suppose $\Gamma=\langle a_1,\ldots,a_k\rangle$ and $a_0\in\Gamma$ is the element you're interested in. You can say $\Gamma=\langle a_0,a_1,\ldots,a_k\rangle$, so then the validity of following sentence can be decided by [Sela, §4]: $$\exists x\ (a_0=x^2)$$ Technically this should begin with $\forall y$ to make an AE sentence, but the AE sentence $$\forall y\exists x\ (y=y)\wedge(a_0=x^2)$$ is equivalent.