Versiones de esta pregunta han sido ampliamente estudiadas, pero no es obvio cuáles son las palabras clave correctas. En este caso, es recomendable buscar en geometría algebraica, en particular el estudio de curvas algebraicas, sobre campos finitos. El teorema relevante en este tema es el límite de Hasse-Weil, que a su vez generaliza ampliamente a las conjeturas de Weil.
El límite de Hasse-Weil implica que si $f$ es irreducible y se cumple cierta condición de no singularidad (en realidad no estoy seguro si esto es necesario), el número de soluciones es algo así como (pero no exactamente)
$$p \pm 2g \sqrt{p}$$
donde $g = \frac{(r-1)(r-2)}{2}$ según la fórmula de género-grado. Esto da un límite que es peor que tu límite si $r$ es grande comparado con $p$ pero que es sustancialmente mejor si $p$ es grande comparado con $r$, por lo que depende de en qué régimen te interese.
Por supuesto, si $r > p$ entonces un límite aún mejor que $rp$ es $p^2$...
Conjeturalmente, el límite de Hasse-Weil debería ser ajustado en un sentido adecuado (en particular, asintóticamente en $p$) por una generalización adecuada de la conjetura Sato-Tate. Por otro lado, en general tu límite puede ser ajustado, ya que $f$ puede ser un producto de factores lineales distintos. Si $f$ es reducible, entonces deberías factorizar $f$ y aplicar el límite de Hasse-Weil por separado a cada uno de sus factores.
