Depends if you're counting the number of cycles in one second, or the elapsed time per input cycle.
If you're counting cycles per second, there's no way to get better resolution that 1 part in 5000, no matter how fast your counter counts. There's always going to be a plus or minus one count error per second.
If you instead time each cycle, you can do much better, especially at lower frequencies.
5000 Hz is 200 microseconds per cycle. Your 10MHz counter will count up to around 2000 in one cycle, so your resolution is 0.05%. If you count multiple cycles, say TEN, then that takes only 2 milliseconds and your resolution is 0.005%.If you count the output of the 1/256 divider, your counter will be up around 500,000, so the resolution is 256 times better.
Guess you should decide whether you want to count cycles per second, or seconds per cycle. At lower frequemcies, the latter has better resolution, at higher ones, the former.