PWM has two important parameters:

- Frequency. There are actually two frequencies involved - the underlying clock frequency, and the frequency of the resulting PWM waveform. (a PWM waveform spends some time high and some time low during each period. The combined time of the low/high is the "period", and the PWM frequency is 1 divided by the period.)
- Resolution. The number of different ways you can divide the period. In order to get 256 different "on" times, the underlying clock frequency has to be 256 times faster than the PWM frequency. If you only need 16 different values, then you only need a clock frequency 16 times the PWM frequency.

The AVR used on the Arduino Uno (and Mega) has a clock speed of 16MHz. So if you want 256 different values, that gives you the 16MHz/256=62.5kHz top frequency. If you only need 32 different values, you could run 500kHz. (Note, however, that using other than 256 will use up some timer resources, and cut the number of pins usable for HW PWM in half.) There are some AVRs (the tiny85, for example) that have a special high-speed clock circuitry for PWM, and can produce higher PWM frequencies (I think 64MHz unerdlying clock, on the tiny85.)