ECC algorithm pollard's $\rho$ complexity
When we say an algorithm is 'exponential' or 'polynomial', when mean that the running time is bounded by an exponential or polynomial function of the size of the input in bits.  That is, the input of the function is not $p$, but $\log p$.  And so, $O(\sqrt p ) = O( e^{1/2 \log p})$ is bounded by an exponential in $\log p$.

Also note that the Wiki article is not talking about the Pollard rho algorithm applied to ECDLP, instead it is talking to Pollard rho applied to factorization.  For the Pollard rho applied to factorization, the time it takes is a factor of $p$, where $p$ is the smaller factor; hence, (because the factors are approximately the same length) $\sqrt p$ is roughly $n^{1/4}$ (with the $polylog(n)$ factor coming into place because Pollard rho isn't perfectly efficient in this scenario).