I don't know how much the accuracy drops if you exceed the recommended rates in the datasheet, but I would think it would not be good practice to add functionality to the standard Arduino platform that clocked the ADC faster then the manufactures recommendation. And if my math is correct, at 16mhz, a prescale of 64 or less will exceed the 200khz max ADC clock rate stated in the datasheet.
The ADC accuracy also depends on the ADC clock. The recommended maximum ADC clock frequency is limited by the internal DAC in the conversion circuitry. For optimum performance, the ADC clock should not exceed 200 kHz. However, frequencies up to 1 MHz do not reduce the ADC resolution significantly. Operating the ADC with frequencies greater than 1 MHz is not characterized.When using single-ended mode, the ADC bandwidth is limited by the ADC clock speed. Since one conversion takes 13 ADC clock cycles, a maximum ADC clock of 1 MHz means approximately 77k samples per second. This limits the bandwidth in single-ended mode to 38.5 kHz, according to the Nyquist sampling theorem.
I wonder if the use of the term resolution rather than accuracy is significant. That note discusses calibrating an ADC, it is not clear what errors an uncalibrated ADC will have if used outside the recommended clock speeds.
For most applications, the ADC needs no calibration when using single ended conversion. The typical accuracy is 1-2 LSB, and it is often neither necessary nor practical to calibrate for better accuracies.However, when using differential conversion the situation changes, especially with high gain settings.
The AVR uses the test fixture's high accuracy DAC (e.g. 16-bit resolution) to generate input voltages to the calibration algorithm.
There are standalone ADC chips which are a lot faster, but I have no experience with them.