Let $|G|=16$ and $G$ contain 12 elements of order 8. I want to show that no such group can exist. (I've verified with GAP and on groupprops that there is no such group, I want to know why.)
I have figured out the following, but am not sure where to find a contradiction.
$G$ must have 3 cyclic subgroups of order 8, which, by counting, all share their subgroup of order 4. This accounts for all the elements of $|G|$. Let $C_2$ be the unique subgroup of order 2 in $G$, then $G/C_2\simeq Q_8$, the quaternion group, since it's the only group of order 8 with 6 elements of order 4.
I'm not sure if any of this is useful, but I don't know where to proceed.
The group $G$ would certainly be generated by two elements, so would have Frattini subgroup of order $4,$ and would have $3$ maximal subgroups, each of which would be cyclic of order $8,$ s you have already noticed. Now $G$ is certainly not cyclic, so every element of $G$ is contained in a maximal subgroup. Now if $x \in M$ and $M$ is maximal, then $\langle x \rangle {\rm char} M \lhd G,$ so $\langle x \rangle \lhd G.$ In particular, if $x$ has order $2,$ then $x \in Z(G).$ Now every proper subgroup of $G$ is cyclic (since all maximal subgroups are), so $G$ contains only one element of order $2$. If $M,N$ are distinct maximal subgroups of $G,$ then $MN = G$ and $|M \cap N| = 4,$ so $M \cap N \leq Z(G)$ ( it is centralized by both $M$ and $N).$ However $G,$ has only one subgroup of order $4,$ which we now know to be $Z(G).$ For $M,N$ as above, and any element $n$ of $N \backslash M,$ and generator $m$ of $M,$ we must have $n^{-1}mn \in \{m^{-1},m^{3},m^{5} \}.$ Since $n$ centralizes $m^{2},$ we must have $n^{-1}mn = m^{5}.$ Hence $[n,m] \in Z(G).$ If follows that $[G,G]$ is cyclic of order $2,$ since $n$ and $m$ were arbitrary elements of order $8$ and elements of order less than $8$ are central. Since $G$ is generated by two elements, we must have $G \cong C_{2} \times C_{4}.$ But then $G/Z(G)$ contains a Klein $4$-group as a maximal subgroup, whereas $Z(G) \leq \Phi(G),$ so every maximal subgroup of $G/Z(G)$ is also cyclic, a contradiction.