Counting cyclic subgroups of order $p^{2}$: $p$ an odd prime vs. $p=2$

The following is true:
The number of cyclic subgroups of order $4$ of some group is odd iff the Sylow $2$-subgroups are cyclic, dihedral, semi-dihedral or generalized quaternion.

As in your proof, it suffices to consider $2$-groups $G$ and look at the number mod $4$ of solutions of $x^2=1$ in $G$. Now Theorem 4.9 in Isaacs' book Character theory of finite groups tells us that when the number $t$ of involutions in a $2$-group is $t\equiv 1 \mod 4$, then $G$ is cyclic or $\lvert G:G'\rvert =4$. (The theorem is ascribed to Alperin-Feit-Thompson, probably the result meant by Geoff in the comments.) Of course, the only other possibility is $t\equiv -1 \mod 4$. A result of Olga Taussky (Satz III. 11.9 in Huppert's Endliche Gruppen I) tells us that the only nonabelian $2$-groups with $\lvert G:G'\rvert = 4$ are the dihedral, semi-dihedral and generalized quaternion groups.
Conversely, the number of cyclic subgroups of order $4$ in each of these groups is indeed odd, and thus also in a group with such a group as Sylow $2$-subgroup.

The proof in Isaacs of that theorem of Alperin-Feit-Thompson uses characters, in particular the Frobenius-Schur indicator.

Added later: Trying to find the original source of Alperin-Feit-Thompson, I found instead a paper of Marcel Herzog, Counting group elements of order $p$ mod $p^2$ (MR466316), which contains (elementary) proofs of the "Alperin-Feit-Thompson"-result and the result for $p$ odd, and references to older proofs in the literature. In his math review, Isaacs also mentions a theorem of Kulakoff concerning the case $p$ odd.