For $p$ prime, $n \geq 1$ and $r \equiv 1 \mod{p}$, let $f(p,n,r)$ be the smallest possible value of $f_p(G)$ among groups $G$ where the largest power of $p$ dividing $|G|$ is $p^n$ and $n_p(G) = r$. This only makes sense if at least one such group exists, so when we talk about $f(p,n,r)$ we assume that this is the case.
Using this notation, the original question could be formulated as follows:
For fixed $p$ and $n$, find a good lower bound for $f(p,n,r)$ in terms of $r$. How does $f(p,n,r)$ grow as $r \rightarrow \infty$?
According to Miller's theorem, $f(p,n,1) = p^n$, $f(p,n,p+1) = p^{n+1}$ and $f(p,n,r) \geq (2p-1)p^n$ when $r \geq 2p+1$. It is also possible to show that $f(p,n,2p+1) = (2p-1)p^n$. See my answer to this question on MO. Also, it's easy to show that $f(p,1,r) = (p-1)r + 1$. Calculating the exact value (even finding a better lower bound) for $f(p,n,r)$ seems difficult in other cases.
Here is an example which suggests that the growth of $f(p,n,r)$ is slow in general. It implies that the growth is slower than linear when $p = 2$ and $n > 1$.
Let $q \equiv 3 \mod{8}$ be prime and let $G = \operatorname{PSL}(2,q)$. Then the Sylow $2$-subgroups of $G$ have order $4$. In this case $n_2(G) = \frac{q(q-1)(q+1)}{24}$ and
$$f_2(G) = \frac{q(q-1)}{2} + 1 = 4 \cdot (n_2(G)\frac{3}{q+1} + \frac{1}{4})$$
For $n \geq 2$, define $H = G \times C_{2^{n-2}}$. Now $n_2(H) = n_2(G)$ and $f_2(H) = 2^{n-2} f_2(G) = 2^n (n_2(G) \frac{3}{q+1} + \frac{1}{4})$.
This shows that $f(2,n,r) \leq 2^n(\frac{3r}{q+1} + \frac{1}{4})$ when $r = \frac{q(q-1)(q+1)}{24}$.
Hence there is no constant $C > 0$ such that $f(2,n,r) \geq Cr$ for all $r \equiv 1 \mod{p}$, since there are infinitely many primes $\equiv 3 \mod{8}$.
Questions: Is there a similar example for $p > 2$? For $n > 1$, is it possible to do any better than $$f(p,n,r) \geq r^{p^{-n}}$$
in general? That is, can we find a lower bound that grows faster than $r^{p^{-n}}$?
(The above inequality follows from the fact that every Sylow $p$-subgroup contains $p^n$ elements from the union of Sylow $p$-subgroups, so $f_p(G)^{p^n} \geq n_p(G)$.)
I like this question, and wanted it to have a bit of a longer answer:
Surprising
This result should be a little surprising. After all the Sylow $p$-subgroups of $H$ can have smaller order, and even though $G$ may have only a few subgroups of order $p^n$, it might have a ton of order $p^{n-1}$. For example, in $G=A_4$, we have only $n_2(G)=1$ Sylow $2$-subgroup, but it has $3$ subgroups of order $2^1$, and so a subgroup $H$ has $n_2(H) \leq 3$, but that leaves open the possibility of $n_2(H) \in \{2,3\}$ both of which contradict the theorem. There is an analogue of $A_4$ called $G=\operatorname{AGL}(1,p^2)$ with approximately the same behavior: $n_p(G)=1$ but $G$ has $p+1$ subgroups of order $p$. When one actually looks for a subgroup $H$, one runs into a problem: no single $H$ contains all those subgroups of order $p$ (or even two of them in the $A_4$ and AGL cases) unless it contains an entire Sylow $p$-subgroup (making those smaller $p$-subgroups irrelevant).
Proof
This idea leads to a simple proof (given by Derek Holt in the comments).
We construction a 1-1 function $f$ from $\operatorname{Syl}_p(H)$ to $\operatorname{Syl}_p(G)$ where $\operatorname{Syl}_p(X)$ is the set of Sylow $p$-subgroups of the finite group $X$. Given a Sylow $p$-subgroup $Q$ of $H$, Sylow's containment theorem says that $Q$ (a $p$-subgroup of $G$) is contained in some Sylow $p$-subgroup $f(Q)$ of $G$. If $f(Q_1) = f(Q_2)$, then $Q_1, Q_2 \leq f(Q_1)$ and $Q_1, Q_2 \leq H$, so $Q_1, Q_2 \leq f(Q_1) \cap H$. However, $f(Q_1) \cap H$ is a $p$-subgroup of $H$, and a $p$-subgroup of $H$ can only contain at most a single Sylow $p$-subgroup of $H$, so $Q_1 = Q_2$. Hence $f$ is a 1-1 function, and $n_p(H) \leq n_p(G)$.
Normal subgroups
If $H$ is a normal subgroup of $G$, then in fact $n_p(H)$ divides $n_p(G)$. Hall (1967) calculated $n_p(G) = n_p(H) \cdot n_p(G/H) \cdot n_p(T)$ where $T=N_{PH}(P \cap H)$ for any Sylow $p$-subgroup $P$ of $G$.
(See also this answer of Mikko Korhonen.)
Best Answer
The elements of order $p$ consist of a $p$-cycle of the form $(1,a_2,a_3,\ldots,a_p)$, where $a_2,a_3,\ldots,a_p$ is a permutation of $2,3,\ldots,p$. So there are exactly $(p-1)!$ elements of order $p$.
Now each subgroup of order $p$ contains $p-1$ elements of order $p$ (i.e. its non-identity elements), and the intersection of any two such subgroups is trivial, so the total number of subgroups of order $p$ is $(p-1)!/(p-1) = (p-2)!$.