Is a wavelet-based correlation measure worth any additional computational overhead?
First off, you should use whichever tool is appropriate for the job.  Correlation vs coherence vs wavelet-based correlation are all different things, so this question is kind of like asking "Which is better? Screwdrivers or hammers?"  It depends on what you're trying to do, and whether you care about similarity in time, frequency spectra, or both.

Second, I have only a minimal understanding of wavelets, but your assumption that wavelets require more computation might be wrong.  The Fast Fourier Transform takes $O(n\log n)$ operations, while the Fast Wavelet Transform takes $O(n)$.  So the wavelet method might actually require less computation, depending on whether you can use the information you get out of it.

Empirically, producing n outputs from n real inputs, the multi-level wavelet transform in PyWavelets becomes faster than NumPy's FFT when n is greater than about 4096. 



However 


It's Python, and the two implementations could be very differently efficient.  I don't even know if wavedec() would be considered a Fast Wavelet Transform.  They use the abbreviation DWT in their documentation.  Are Haar DWT and FWT the same thing?
The time varies depending on the wavelet used.  Meyer wavelet takes 6 times as long as Daubechies to produce the same amount of data.
I still don't understand how the FWT tiles the time-frequency plane, or if producing n outputs is sufficient to get the same kind of similarity measurement as an n-point circular cross-correlation using FFTs. (Technically it's a time-scale plane, not time-frequency, but I think they're the same for the complex Morlet wavelet?)  FWT is a "critical sampling" of the plane, and produces the same amount of data as FFT, so it seems fair to compare them.


The main point is that computation time is at least roughly similar for both, so I don't think you should worry about it when deciding which to use.