In this paper, we derive explicit formulae for the number of regular even-valent graphs, with fixed minimal embedding genus, in which both the valence parameter and the number of vertices are allowed to vary. Our results extend the explicit formulae of Ercolani--McLaughlin--Pierce (2008) for genus $0$ and of Ercolani--Lega--Tippings (2023) for genus $1$. More precisely, we obtain explicit counts $\mathscr{N}_g(2ν,j)$ -- with $ν$ and $j$ as variables -- of graphs with $j$ vertices of uniform valence $2ν$ and minimal embedding genus $g$, for $2\leq g\leq 4$. We also obtain the corresponding formulae for the two-legged counts $\mathcal{N}_g(2ν,j)$. The method applies to $g\geq 5$, with increasing computational effort as $g$ increases. Finally, we derive leading-order large-valence asymptotics for these counts when $g\leq 4$, and formulate a structural conjecture for higher genus.