Efficient frequency offset estimation of known signals
Time aligned
If the signals are time aligned, you can conjugate-multiply the received signal with the reference signal and look for the dominant frequency.
Max-Likelihood estimation of the frequency shift and complex gain of a known signal in Gaussian Noise
Let $\vec r$ be the noisy observation of a frequency translated version of a sent $\vec x$ with unknown gain.
Here, let us consider the channel $\mathbf A \in \Gamma$
$$
\vec r = \mathbf A \vec x + \vec w  \in \mathbf C^N \\
[\mathbf A]_{nn} = \rho \exp(\omega n) , \rho \in \mathbf C^N , \omega \in \mathbf R \\
[\mathbf A]_{mn} = 0, \forall m \ne n  \\
p(\vec w|\tau) \propto \exp\left( \frac {-\| \vec w \|^2} {\tau}  \right) 
\\
\mathbf A^* \triangleq 
\operatorname*{argmax}_{\mathbf A}
\max_{\tau}
\underbrace{p(\vec r| \mathbf A,\vec x ,\tau)}_{  \propto \exp \left( \frac {-\| \mathbf A \vec x - \vec r \|^2} {\tau}  \right) }
\\
\mathbf A^* =
\operatorname*{argmax}_{\mathbf A}
\underbrace{
-\| \mathbf A \vec x - \vec r \|^2
}_{
\triangleq f(\mathbf A)
}
\\
f(\mathbf A)
=
- (\mathbf A \vec x - \vec r )^H
(\mathbf A \vec x - \vec r )
\\
= - \vec x^H 
\underbrace {\mathbf A^H\mathbf A }_{|\rho|^2 \mathbf I
}
\vec x
+ 2\mathop{re}
(\mathbf A \vec x)^H \vec r 
-
\underbrace
{\vec r^H \vec r}_{
\|\vec r\|^2}
$$
Notice the first and third terms have no dependence on frequency $\omega$ nor the phase of $\rho$.  So we simply need to find the frequency that best aligns $\vec x,\vec r$.  That will imply the phase.
$$
\omega^* = \operatorname*{argmax} \sum_n |\exp(-j\omega n) \bar {x_n} r_n|^2
$$
One can use an FFT or some such frequency estimator to recover the dominant frequency
Not Time-Aligned
If the signals are not time-aligned, then you've got a time and frequency search problem on your hand.  With low SNR, this is essentially the problem solved by the cross-ambiguity function (CAF).  If you've got several dB of margin you can take a shortcut.
If you have a reference signal with some AM variation; you can time-align first by AM detecting both signals and then correlating your input by the reference AM.  If your  reference signal doesn't have much amplitude variation, but its spectrum is &quot;spikey&quot; you might be able to correlate the magnitude spectra of the received and reference.  This is the same trick applied in the frequency domain, rather than time domain.
With the exception of the CAF, these are all fairly cheap operations.