Number of subgroups of prime order
Here's another approach. Consider the solutions to the equation $x_1x_2\cdots x_p=1$ in the group $G$ of order divisible by $p$. Since there is a unique solution for any $x_1,\ldots,x_{p-1}$, the total number of solutions is $|G|^{p-1}$, which is divisible by $p$. If $x_1,x_2,\ldots,x_p$ is a solution, then so is $x_2,x_3,\ldots,x_p,x_1$, and so we have an action of the $p$-cycle $(1,2,3,\ldots,p)$ on the solution set.
Since $p$ is prime, the orbits of this action have size $p$ if $x_1,x_2,\ldots,x_p$ are not all equal, and size 1 if they are all equal. So the number of solutions of $x^p=1$ is a multiple of $p$. Now use Steve D's hint to complete the proof.
Incidentally there is a theorem of Frobenius that says that for any $n>0$ and any finite group of order divisible by $n$, the number of solutions of $x^n=1$ is a multiple of $n$.
On the off chance you like graph theory, here is a silly use of the commuting graph to organize the count:
Let V be the collection of subgroups of G of prime order p. Let E be all pairs $(P,Q)$ where P and Q are subgroups of order p that commute: xy = yx for all x in P and y in Q.
Lemma: If $\langle x\rangle$ and $\langle y\rangle$ are not neighbors, then neither are $\langle x \rangle$ and $\langle x^{-i} y x^i \rangle$ for any $i$.
Proof: If $x x^{-i} y x^i = x^{-i} y x^i x$, then multiply $x^i$ on the left and $x^{-i}$ on the right to get $x y = y x. \square$
Since x has order p, that means any non-neighbor y actually gives p different non-neighbors.
Lemma: The non-neighbors of x come in batches of p.
That is pretty nice, since it means we can ignore most of the graph if we are only counting vertices mod p: we only need to look at the neighbors of x. It gets even better though:
Lemma: If x and z are neighbors, but y is not a neighbor of x, then $z^{-i}\langle y \rangle z^i$ is also not a neighbor of x.
The proof is actually the same as before, since we only used that $x$ and $x^i$ commuted in the previous proof, and now we use that $x$ and $z^i$ commute.
This means not only can we ignore non-neighbors of x, but we can choose another neighbor z of x, and ignore anyone who is not a neighbor of both x and z! Hopefully you see how we can continue:
Lemma: If X ⊆ V is a collection of vertices that are all mutual neighbors (a so-called clique), then the vertices that are not neighbors of all of them come in batches of p.
So we keep applying this until we get a maximal clique, and we know that everything outside of the clique comes in batches of p, so we just want to know how big a maximal clique is.
Lemma: A maximal clique is just (the order p subgroups of) an elementary abelian p-group, and in particular has $$\frac{p^k-1}{p-1} \equiv \frac{-1}{-1} = 1 \mod p$$ subgroups of order p, where $p^k$ is the size of the elementary abelian subgroup.
This finishes the problem. :-)
If g is any element of G, then $g^{-1}Pg$ is in V if and only if P is in V, and $(g^{-1}Pg,g^{-1}Qg)$ is in E if and only if $(P,Q)$ is in E, so of course G acts on the graph, but typically not vertex or edge transitively.
In case you like working examples first, here is a similar explanation, but making reference to a standard example of the symmetric group on 4 points.
As an example, when G is the symmetric group on 4 points, then $$V = \{ \langle(12)\rangle, \langle(13)\rangle, \langle(14)\rangle, \langle(23)\rangle, \langle(24)\rangle, \langle(34)\rangle, \langle(12)(34)\rangle, \langle(13)(24)\rangle, \langle(14)(23)\rangle \}$$
and the edges look like:
(source: uky.edu)
Now consider $g^{-1}Pg$ for g an element of order p. Either we get a new vertex, or $(\langle g \rangle, P)$ is an edge of the graph. If we get a new vertex, then it is easy to check we actually get p distinct vertices, none connected to $\langle g \rangle$, $P, g^{-1} P g, g^{-2} P g^2, \dots, g^{1-p} P g^{p-1}$.
For instance if we take $g=(14)(23)$ and $P=\langle(24)\rangle$, then we get both $P=\langle(24)\rangle$ and $g^{-1}Pg=\langle(13)\rangle$. So this g leaves 5 vertices alone, and swaps two pairs of vertices.
We thus have two very different kinds of vertices: the kinds that are connected to g, and the kinds that are not. The kinds that are not come in bunches of size p, so we can ignore them as we only are counting mod p. We thus can concentrate only on the neighborhood of g, which is normally called something like $\Lambda(C_G(g))$, but for us, it is just a bunch of stuff that commutes with g.
Here is a bit of trick that makes things almost too easy: what is so special about g? We still have this weird bowtie graph in the example, and honestly I prefer triangles. Well, I'll repeat the argument for $h=(12)(34)$, but since g and h commute, I still only have to consider the neighborhood of g (still the bow-tie). So we have three kinds of vertices: the kind that commute with g and h, the kind that commute with g but not h (and therefore h swirls them around in bunches of size p), and the kind that don't commute with g (and therefore g swirls them around in bunches of size p).
In other words, I can keep choosing neighbors until I am reduced to a complete subgraph (a clique), because people who don't know each other get put together in bunches of size p.
Once I am down to a complete graph, what do I have? Just a bunch of elements of order p that all commute with each other, so an elementary abelian group of order $p^k$ containing exactly $(p^k-1)/(p-1) \equiv (-1)/(-1) = 1 \mod p$ subgroups of order p.
Here is a strategy that may work.
Reduce to the case of $p$-groups: show that if $G$ is a group and $P$ a Sylow $p$-group, $c(G)$ the number of subgroups of order $p$ in $G$ and similarly for $c(P)$, then $c(P) \equiv c(G) \pmod p$. (Let a Sylow subgroup act on the subgroups of order $p$ and try to imitate some proof of Sylow's theorem. It's been asked recently on these boards but a search turned out empty, maybe you're more lucky.)
Try the case of (finite) abelian $p$-groups: they're all of the form $C_{p^{a_1}} \times C_{p^{a_2 }} \times \dots \times C_{p^{a_k}}$. Elements that satisfy $x^p=1$ are all of the form $(g_1,g_2,\dots,g_k)$ where $g_i^p = 1$ for all $i$. There are $p^k$ such elements, but one of these is $1$. Then think of Steve D's comment below your question.
Now consider case of a general $p$-group $P$ of order $p^i$ and let $P$ act on $X$, the set of elements of order $p$. Because trivial orbits lie in the center $\mathbf Z(P)$, conclude that $|X| = (p^k-1) + \ell p$ for some $k$ and $\ell$. This number must be divisible by $p-1$. (Steve's comment again.) Since $p\perp p-1$, this implies that $p-1 \mid \ell$. Then calculate $|X|/(p-1) \pmod p$.