Defining a graph decision problem not in NP
Problems of the type "Count the number of [object]", where "[object]" is something that can be verified in polynomial time, are essentially what defines the class $\#P$ ($\textrm{Sharp-}P$). $\#P$ is the counting variant of $NP$.

As pointed out by @D.W., the problem you picked just so happens to be in $P$, but if you had picked some other problem (such as counting simple paths) it would have been $\#P$-complete.

If you take a $\#P$-complete counting problem, then the decision-counting variant ("are there at least $x$ many objects [...]") can not be in $NP$, unless the polynomial hierarchy collapses. This follows by Toda's theorem, which states that $PH\subseteq P^{\#P}$. If such a decision-counting problem would be in $NP$, we could use a polynomial number of calls to an $NP$ oracle to compute the exact number (by binary search). Thus $P^{\#P}$ would be equal to $P^{NP}$ and the polynomial hierarchy collapses.