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.
Still, the Atmel document referred to above (http://www.atmel.com/dyn/resources/prod_documents/DOC2559.PDF) says:
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.
To me, that's as good as a green light, direct from the manufacturer, to go to 1 MHz and a 77k sample rate--with no significant effect on resolution.