Zero padding in frequency domain, any tricks to speedup?
It looks like your choice is based on whether (approx) 5*NLogN (IFFTs+FFTs) is greater or lesser than N^2 (linear convolution).

You could use coarser interpolation methods (cubic, spline, etc.) to upsample the spectra but the error would likely be audible as a clear loss in quality.