I found this question while searching for some hints for the same problem. Here is the way I found to solve this problem.
Let $G$ be a finite abelian group. We induct on the order of $G$. If $\lvert G\rvert=1$, then we know that the only divisor of the order is $1$, and we are done. Next, suppose that $\lvert G\rvert=n$, and that the statement holds for $k<n$. Let $d\in \mathbb{N}$ be a divisor of $n$, $d|n$. We can decompose $d=kp$, for some prime $p$ and $k\in \mathbb{N}$. By Cauchy's Theorem, there exists a subgroup $H\le G$ of order $p$. We can form the quotient group because $G$ is abelian, so $H$ is normal.
Then, $\lvert G/H\rvert$ satisfies the inductive hypothesis, since $\lvert G/H\rvert<n$. So, we have that all of the divisors of $|G/H|$ correspond to a subgroup of $G/H$ with appropriate order. In particular, $k$ divides $\lvert G/H\rvert$. By the inductive hypothesis and the Lattice Isomorphism Theorem, we have a subgroup $H\le K\le G$ such that $K/H\le G/H$ and $K/H$ has order $k$. Since $H$ is finite, this implies that $\lvert K\rvert=k\lvert H\rvert=kp=d.$ So, we have a subgroup of order $d$. This completes the induction. $\blacksquare$
I think the answer is yes, $p^4$ divides $|G|$. Here is a sketch of how to prove this. This argument seems a bit long and tortuous, and there might be an easier proof. I will just do it for odd $p$. A similar but slightly different argument works for $p=2$.
Let $N = \Phi(G) = C_p \times C_p$, and $N \le P \in {\rm Syl}_p(G)$.
Now $N$ cannot have a complement in $G$, since otherwise that complement would be contained in a maximal subgroup that did not contain $N$. So by a theorem of Gaschütz, $N$ does not have a complement in $P$. So $N < P$, and we only have to consider the case when $|P|=p^3$. Then, for elements $g \in P \setminus N$ must have order $p^2$, with $g^p \in N$.
Now the conjugation action of $G$ on $N$ induces a subgroup $\bar{G} = G/C_G(N)$ of ${\rm Aut}(N) = {\rm GL}(2,p)$. If the image $\bar{P}$ of $P$ in $\bar{G}$ is not normal in $\bar{G}$, then $\bar{G}$ has more than one Sylow $p$-subgroup. But any two Sylow $p$-subgroups of ${\rm GL}(2,p)$ generate ${\rm SL}(2,p)$.
Since we are assuming that $p$ is odd, ${\rm SL}(2,p)$ has a central subgroup $\bar{T}$ of order $2$ that acts as $-I_2$ on $N$. Let $T$ be the complete inverse image of $\bar{T}$ in $G$ (so $|T/C_G(N)|=2$). Then $T \lhd G$. Let $S \in {\rm Syl}_2(T)$. Then, by the Frattini Argument, $G = TN_G(S)$. So $p$ divides $|N_G(S)|$, but $N_G(S) \cap N = 1$, so a Sylow $p$-subgroup of $N_G(S)$ has order $p$ and complements $N$, contrary to what we said above.
So $\bar{P} \unlhd \bar{G}$. But then $M := \langle g^p \mid g \in P \rangle$ is a normal subgroup of $G$ of order $p$ contained in $N$. The image $N/M$ of $N$ in $M$ has a complement in $P/M$, and hence, by Gaschütz's theorem again, $N/M$ has a complement $H/M$ in $G/M$. Then $|G:H|=p$ and $H$ is a maximal subgroup of $G$ not containing $N$, contradiction.
Best Answer
Here is a proof that, for a finite group $G$, $|G/\Phi(G)|$ is divisible by all primes $p$ dividing $|G|$. It uses the Schur-Zassenhaus Theorem. I don't know whether that can be avoided.
First note that each Sylow $p$-subgroup $P$ of $\Phi(G)$ is normal in $G$. (So, in particular, $\Phi(G)$ is nilpotent.) To see that, we have $G = \Phi(G)N_G(P)$ by the Frattini Argument, and then by the fact that $\Phi(G)$ consists of the non-generators of $G$, we have $G = N_G(P)$.
Now if there is a prime $p$ dividing $|G|$ but not dividing $|G/\Phi(G)|$, then $\Phi(G)$ contains a Sylow $p$-subgroup $P$ of $G$ and $P \unlhd G$. So, by the Schur-Zassenhaus Theorem, $P$ has a complement $H$ in $G$. Let $M$ be a maximal subgroup of $G$ containing $H$. Then $p$ divides $|G:M|$ and hence $p$ divides $|G/\Phi(G)|$, contradiction.