Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?

Geometrically this means we have to sort through a positive proportion of the affine plane before being sure we have counted all solutions (modulo the complexity of addition and multiplication).

Non-example: the solutions of $x+y=0$ are counted in $O(\log p)$ time as there are $p$ solutions.