Edge devices are being deployed at increasing volumes to sense and act on information from the physical world. The discrete Fourier transform (DFT) is often necessary to make this sensed data suitable for further processing -- such as by artificial intelligence (AI) algorithms -- and for transmission over communication networks. Analog in-memory computing has been shown to be a fast, energy-efficient, and scalable solution for processing edge AI workloads, but not for Fourier transforms. This is because of the existence of the fast Fourier transform (FFT) algorithm, which enormously reduces the complexity of the DFT but has so far belonged only to digital processors. Here, we show that the FFT can be mapped to analog in-memory computing systems, enabling them to efficiently scale to arbitrarily large Fourier transforms without requiring large sizes or large numbers of non-volatile memory arrays. We experimentally demonstrate analog FFTs on 1D audio and 2D image signals, performing analog computations on up to 524K charge-trapping memory devices simultaneously, where each device has precisely tunable, low-conductance analog states. The scalability of both the new analog FFT approach and the charge-trapping memory device is leveraged to compute a 65,536-point analog DFT, a scale that is otherwise inaccessible by analog systems and which is $>$500$\times$ larger than any previous analog DFT demonstration. Analog FFT cores can provide higher energy efficiency and performance per area than specialized digital FFT processors at all FFT sizes, while also functioning as efficient matrix multiplication engines for AI workloads.