MHz Sampling Rate for Arduino
The problem with driving the ADC faster is that the S+H circuit won't have enough time to reach the final value before the conversion is performed, meaning that precision will be lost.

The best thing to do would be to use an external ADC from e.g. TI or Microchip that has the capabilities you're looking for.