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: it takes $O(\log p)$ time to count (and output) the $\mathrm{mod}\:p$ solutions of $x+y=0$ as there are $p$ solutions.