How do we recover units of force from units of gravitational potential?

You are using a wrong relation. The relation is not

• "force equals the negative gradient of gravitational potential" but

• "force equals the negative gradient of gravitational potential energy":

$$F=-\nabla U= -\frac{dU}{dx}$$

The $U$ here is potential energy, not potential. A potential is rather a potential energy per mass.

Had you used potential energy to derive the force unit, you would indeed have gotten the correct force unit of $[\mathrm{\frac{kg \; m}{s^2}}]=[\mathrm{N}]$. But using potential to derive the unit, you get not the unit of force but that of force per mass, $[\mathrm{\frac{kg \; m}{s^2}/kg}]=[\mathrm{\frac{m}{s^2}}]=[\mathrm{\frac{N}{kg}}]$.

This is why (due to the "per-mass" feature) you are lacking one $\mathrm{kg}$ in the derived unit.

I find the easiest way to remember the dimensions of the units is to start from the second law:

$$ F = ma $$

then work (which is a form of energy) is force times distance.

The units of acceleration are m/sec$^2$ so that's $LT^{-2}$. And multiplying by mass gives us the dimensions of force $MLT^{-2}$, then multiplying by distance gives us the dimensions of energy $ML^2T^{-2}$.

When you take the gradient of the potential energy, $dU/dx$, you are in effect dividing by $L$, so you get back $MLT^{-2}$. And those are of course the dimensions of force.

You started with the gravitational potential, which is the potential energy per unit mass. As a result you obtain the force per unit mass, which in the acceleration, with unit $m/s^2$.

By the way, the mksi unit of force is the Newton ($kgm/s^2$).