The patent for Autotune can be found here: https://www.google.com/patents/US5973252?dq=5,973,252

My (very non-expert) reading of the patent is that it uses sample reduction and some specific features of the periodic form of the human voice to simplify the math involved in the auto-correlation routine. Although this routine does seem to be unique as far as I know, I wouldn't be surprised if it shares similarities to other techniques to reduce correlation complexity.

Polyphase filters maybe? It's an approach used primarily in resampling, and its an easy way to skip a LOT of Multiply-by-zero-and-Accumulate-ing

It decoded to a phase vocoder on the nearest semitones.

read the patent - all time domain, no phase vocoder involved.

> “I realized that most of the arithmetic was redundant, and could be simplified,” he says. “My simplification changed a million multiply adds into just four.”

Doesn't sound like FFT.