What is the most efficient method of storing statistics in an FPGA?
The following is the killer requirement:


  There are a large number of statistics that the design will be
  calculating, and any number of them could be updating every clock
  cycle.


That alone means that you can't lump accumulators together into block RAM's or do any other special tricks to reduce logic requirements.  If you want to make things more efficient then you have to figure out how to change this requirement.

Here are some ideas on how this could happen:


Run your "master clock" at a much higher frequency than your "counting clock".  For example, if your "counting clock" was running at 10 MHz then run your master clock at 160 MHz-- or 16 times faster.  In this way you can process 16 accumulators in a "time slice" fashion.  You'd use some LUT based RAM to make a 16 word dual-port ram.  On the first clock you would process "channel 0", the second clock you'd process "channel 1", etc.  Since your data can only come in at 1/16th of your master clock rate you can process all data in the required time.  This might not work if your master clock rate is too high for your chosen FPGA.  I would estimate that the logic size with this approach is about 1/4th, when compared to just doing a lot of counters.  If you need more than 16 accumulators then you need several of these modules.
If your "counting clock" is too high for approach #1, but the total number of "counts" in a certain time interval is small (even though they could come in all bunched up in time) then you could do something a little more strange.  Start with a FIFO that is 32 or even 64 bits wide.  Each data bit represents a signal for that channel's count to increment.  If, during any one clock cycle, a data bit is set then that "word" is written to the FIFO.  On the output side of the FIFO create some logic that will take a word and use the set bits to increment counters in RAM.  You have to be a little smart here so that if, for example, 4 bits are set then it will take 4 clock cycles to increment those 4 counters.  The counters (32 or 64 of them) are stored in RAM (LUT or Block, whichever makes sense).  The depth of the FIFO will dictate just how bunched up the "count events" can be.  I estimate that this logic will be approximately 1/4th the size, but there is a lot of variation here depending on the width and depth of the FIFO and what kind of RAM is used.  On average you will be limited to incrementing one counter every clock cycle, but the FIFO will soak up any short-term peaks in your count rate.
If you need to count things really fast, but for a very short amount of time then you could simply use a variation on #2.  Make the FIFO really large and don't worry too much about emptying the FIFO quickly.  This assumes that all of your count events will fit in the FIFO.  It's quick and simple, but you are limited to about a few thousand clock cycles for your measurement period.


One difficulty with approach #1 and #2 is that you need crazy logic to clear the counters.  I recommend that you simply don't clear them.  Instead, read the count values at the start and again at the end and then calculate the difference.  I'm assuming that you have a CPU that you can do this in.  This trick will save you lots of logic and some headache.