It's actually easy to put a bound on $Aut(P)$ for some finite $p$-group $P$, simply using Burnside's basis theorem, which says every basis for the elementary abelian group $P/\Phi(P)$ corresponds to a minimal generating set for the group $P$. Clearly, any element of $Aut(P)$ must take one minimal generating set to another.
So how many minimal generating sets are there? Well, if $|\Phi(P)| = p^d$, and $|P/\Phi(P)|=p^e$, then a minimal generating set consists of $e$ elements. There are $$ \prod_{k=1}^{e-1} (p^e-p^k) $$$$ \prod_{k=0}^{e-1} (p^e-p^k) $$ different bases of $P/\Phi(P)$ (as a vector space of dimension $e$). Each such element really represents a coset of $\Phi(P)$, which contains $p^d$ elements; that is, for such a given basis, each basis vector has $p^d$ choices up in $P$; all told, then, there are $$ p^{de} \prod_{k=1}^{e-1} (p^e-p^k) $$$$ p^{de} \prod_{k=0}^{e-1} (p^e-p^k) $$
minimal generating sets. Of course, $Aut(P)$ acts on these freely (as it is defined by what it does to a generating set), so its order divides that number.