Whatever you're reading is based on the idea of starting the timer, waiting for it to reach its maximum, and counting how many events happened between when the timer started and when it stopped. If you divide that count by how long you were waiting, you'll have the average frequency of events during the interval.
Now think: 0.001 Hz is one event per 1,000 seconds.
For a timer running at 16MHz to count up to 2^32-1 will take a little bit over 268 seconds. About 3/4 of the time, it won't even count one cycle of your 0.001Hz signal. Even at 0.002Hz it will measure zero about as often as not.
If you decrease the timer to 8MHz, it will take about 537 seconds to reach 2^32-1. A little bit better, but we're not really there yet.
Decrease it further to 4MHz, and it will take about 1,074 seconds to reach 2^32-1. That's an awfully long time, but now we can reliably tell the difference between 0.001Hz and 0.002Hz.
You might say: you're not actually interested in a 0.001Hz signal, it's just that you want to be able to tell the difference between 500.000Hz and 500.001Hz. That doesn't matter. In a thousand seconds, a 500.000Hz signal will have 500,000 cycles and a 500.001Hz signal will have 500,001 cycles. If you wait less than a thousand seconds, the difference will be less than one cycle and you won't be able to count it.
You might say: well, why use this technique of counting how many events happen before the timer reaches 2^32-1? Why wait so long? Can't we just use the timer to measure the time between two events? That should be faster! And that's partially true. If the frequency you're measuring really is 0.001Hz, of course, then just waiting for two events to happen will still take a thousand seconds (in fact, anywhere between 1,000 and 2,000 seconds, because we have to wait for the first one before we can start counting the time until the second one). But say it's around 500Hz, then you only need to wait a few milliseconds, right? Well, almost.
The thing is, your fastest clock is still 16MHz. At 500.000Hz that's 32,000 cycles between events. What if the frequency is 500.001Hz? That's 31,999.936 cycles between events. Oops, that's no good. We can't measure 0.064 of a clock cycle. To tell the two signals apart we would need to count more events. In this instance, 16 of them would do. The 500.000Hz signal would take 32ms (512,000 clock cycles) while the 500.001Hz signal would take 31.99994ms (511,999 clock cycles). To be safe, we might want to double or triple that to account for jitter and the fact that we don't know the alignment between the measured signal and our free-running clock.
So using this technique we get higher frequency resolution, but the resolution is dependent on the input frequency, unlike the other technique. The higher the frequency measured, the more finely we can measure. If you really need to go down near 0Hz, it doesn't help.
And no matter what technique you use, there will always be a tradeoff where the more accurately you want to measure frequency, the longer you have to wait. That's what your slower timer is accomplishing — making you wait longer for each measurement.