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
Consider the set of supplements to $N$ in $G$. That is, let $$\mathcal{X} = \{H \leq G : HN = G\}.$$ Clearly $\mathcal{X}$ is non-empty because $G \in \mathcal{X}$. Now let $K$ be a minimal element of $\mathcal{X}$, in the sense that $K$ does not contain properly any other element from $\mathcal{X}$. By definition of $\mathcal{X}$ we have $KN = G$. Now let $M$ be a maximal subgroup of $K$. We argue that $K \cap N \leq M$. Once we have proved that, it will follow that every maximal subgroup of $K$ contains $K \cap N$, thus $K \cap N \leq \Phi(K)$.
Suppose for a contradiction that $K \cap N$ is not a subgroup of $M$. Since $N$ is normal in $G$, $K \cap N$ is normal in $K$. So $K \cap N$ permutes with every subgroup of $K$, thus also with $M$. So $(K \cap N)M$ is a subgroup of $K$ which contains $M$ properly. Therefore $K = (K \cap N)M$. Now notice that $$G = KN = (K \cap N)MN = (K \cap N)NM = NM = MN,$$ so $M$ supplements $N$ in $G$, against the minimal choice of $K$. We see, therefore, that $K \cap N$ is contained in every maximal subgroup of $K$ and so $K \cap N \leq \Phi(K)$, as wanted.