The following argument proves that for almost all $p\le x$, there is are $m,n\le p^{1/2+\epsilon}$ with $mn\equiv1 \pmod p$.
Indeed, let $$ P=\{x/2<p\le x: m\le x^{1/2+\epsilon}\ \implies\ \overline{m}\pmod p>x^{1/2+\epsilon}\}. $$ Let $q$ be a prime in $(x^{1/2-\epsilon/2},x^{1/2-\epsilon/3}]$. If $1+kp\equiv 0\pmod q$ for some $k\le x^{\epsilon/2}/2$, then $1+kp=qd$ for some $d\le (1+kx)/x^{1/2-\epsilon/2}\le x^{1/2+\epsilon}$. In particular, $p$ is not in $P$. Therefore, if $p$ is counted by $P$, then for each $q\in (x^{1/2-\epsilon/2},x^{1/2-\epsilon/3}]$, it must avoid the congruence classes $\{-\overline{k}\pmod q: 1\le k\le x^{\epsilon/2}/2\}$. Since $p$ is prime is prime, it must also avoid the classes $0\pmod q$ for all primes $q\le \sqrt{x}$. We then apply the arithmetic form of the Large Sieve (see, e.g., page 159 in Davenport) to conclude that $$ \#P \ll \frac{\pi(x)}{x^{\epsilon/2}} , $$ which proves the claim.
The above result is essentially sharp: the number of $p\in(x/2,x]$ for which there are $m,n\le p^{1/2}(\log p)^c$ with $mn\equiv 1\pmod p$ is $o(\pi(x))$ for small enough $c$. Indeed, we would then have that there is some $k\le (\log x)^{2c}$ such that $1+kp$ can be written as $1+kp=mn$ with $m\le n\le x^{1/2}(\log x)^c$. In particular, $1+kp$ would have a divisor $m\in[0.1k\sqrt{x}/(\log x)^c, \sqrt{1+kx}]$. The number of such primes $p\in(x/2,x]$ is $$ \asymp f(k) \frac{x}{\log x} \frac{1+\left(\log\frac{(\log x)^{2c}}{k}\right)^\delta}{(\log x)^\delta(\log\log x)^{3/2}}, $$ where $\delta=1-(1+\log\log2)/\log 2$ is the constant appearing in Erdos's multiplication table problem and $f(k)$ is some tame multiplicative function that is usually $\asymp1$ (see http://arxiv.org/abs/math/0401223 and http://arxiv.org/abs/0905.0163; this result is not stated there but it should follow from the methods). Summing over $k\le(\log x)^{2c}$, we find that the number of $p\in(x/2,x]$ for which there are $m,n\le p^{1/2}(\log p)^c$ with $mn\equiv 1\pmod p$ is $$ \ll \frac{x}{\log x} \frac{(\log x)^{2c}}{(\log x)^\delta(\log\log x)^{3/2}} . $$ Taking $c=\delta/2$ yields the claimed result.
The above line of thought should be able to produce, at least heuristically, the optimal value of $c$ for which the following two propositions hold: $$ \#\{p\le x: \exists m,n\le p^{1/2}(\log p)^{c+\epsilon}\ \text{with}\ mn\equiv 1\pmod p\} \sim \pi(x) $$ and $$ \#\{p\le x: \exists m,n\le p^{1/2}(\log p)^{c-\epsilon}\ \text{with}\ mn\equiv 1\pmod p\} =o(\pi(x)). $$ The point is that if $k\neq k'$, then the multiplicative structures of $1+kp$ and of $1+k'p$ should be independent from each other. Therefore the events that $1+kp=mn$ for some $m,n$ in some range and that $1+k'p=m'n'$ for some $m',n'$ in some range should be independent. So a Borel-Cantelli argument would then yield the optimal value of $c$.