Catastrophic cancellation will occur when $\bar{f}=\frac{1}{n} \sum_i f(x_i)$ is large, positive and nearly equal to $\bar{g}^2 =\left( \frac{1}{n} \sum_i g(x_i) \right)^2$.
If all the $f(x_i)$ are non-negative (which was confirmed in comments):
Let $y_i = f(x_i)^\frac12$. Let $g_i=g(x_i)$ and similarly for $f$.
\begin{eqnarray}
\frac{1}{n} \sum_i (y_i-m)^2
&=&\frac{1}{n} \sum_i (y_i^2-2y_i m + m^2)\\
&=&\frac{1}{n}\sum_i y_i^2-2m\sum_i (y_i - m)\\
&=&\frac{1}{n}\sum_i f_i-2m \bar{e}_y \text{ ... }\text{ where } \bar{e}_y=\frac{1}{n}\sum_i (y_i - m)\\
\end{eqnarray}
\begin{eqnarray}
\left( \frac{1}{n} \sum_i (g_i-m) \right)^2
&=&\left( \frac{1}{n} (\sum_i g_i)-m \right)^2\\
&=& (\bar{g}-m)^2 \\
&=& \bar{g}^2-2\bar{g}m+m^2\\
&=& \bar{g}^2-2m(\bar{g}-m) \\
&=& \bar{g}^2-2m\bar{e}_g
\end{eqnarray} where $\bar{e}_g=\frac{1}{n}\sum_i (g_i - m)$
Hence
\begin{eqnarray}
\frac{1}{n} \sum_i f_i - \left( \frac{1}{n} \sum_i g_i \right)^2
&=& \frac{1}{n}\sum_i f_i-2m \bar{e}_y + 2m \bar{e}_y - (\bar{g}^2-2m\bar{e}_g) - 2m\bar{e}_g\\
&=&\frac{1}{n} \sum_i (y_i-m)^2-\left( \frac{1}{n} \sum_i (g_i-m) \right)^2 \\
& & \quad +2m (\bar{e}_y - \bar{e}_g)
\end{eqnarray}
So $\hat{Q}=\hat{Q}_m + 2m (\bar{e}_y - \bar{e}_g)$
where $\hat{Q}_m=\frac{1}{n} \sum_i (y_i-m)^2-\left( \frac{1}{n} \sum_i (g_i-m) \right)^2$.
There's still subtraction here (both inside the summations and at the end), but if $m$ is reasonably well-chosen it should lead to considerably less loss of accuracy.
Advice: Choose $m$ in the rough ballpark of either $\bar{y}$ or $\bar{g}$, whichever is easier. They should be about the same (or the cancellation would not have been so catastrophic). If the calculation is not "on-line", average a few randomly selected $g$'s or average a few randomly selected $y$'s as is convenient; if both are convenient, you could even do both and average them.
If there's cancellation of any consequence in the difference of $\bar{e}$ terms a better choice of $m$ might be called for but you can also compute each term in the difference $=(y_i-g_i)$, subtract those term by term and average those instead. This is not likely to be an issue.
If you happen to have $\bar{g}$ before this step of calculating $\hat{Q}$, use that for $m$ and drop the remainder adjustment for the $g$ term (which is $0$).
In many cases, even just $m=g_1$ may suffice, so this might be used online (since $g_1$ will be available at the start).
Note that one could adapt Welford's algorithm to this purpose in very similar fashion and obtain a more stable online algorithm still.
whuber points out in comments an even simpler approach that doesn't rely on the individual $f_i\geq 0$, just $\bar{f}$ itself (which should always be the case if you're getting catastrophic cancellation with $\bar{g}^2$).
Let $a=\bar{f}^\frac12$. Then $\hat{Q}=(a-\bar{g})(a+\bar{g})$. Now that first term will still have cancellation in it, but the impact should tend to be smaller.
Having played around with it a bit, it seems that it does often help but it turns out it's not always better, if found some examples fairly quickly where sometimes it makes the error worse. It might well work fine in your application but there are numerous alternatives that might be used. I'd expect the error here mostly comes in the cancellation from $\sqrt{\bar{f}}-\bar{g}$ (rather than in computing the square root), and in that case you could improve the accuracy of that part if its at issue, but if you need to take that step this approach that may not offer much benefit over a more direct one.
