Well, the important point here that you have to remember is that, in general, work depends on how you do it. By this I mean, in your example, that if you lift the object strongly so that when it reaches a height $h_f$ it has some velocity, then the work you have done will not be $W = M g (h_f - h_i)$ (let me use the more usual letter $W$ for work). So, what is hidden in the expressions you use to calculate work?
There are basically two things. First of all, when you write:
$$ W = M g (h_f-h_i) \; ,$$
you assume that you start with an object at rest at a height $h_i$ and that you end up with the same object at height $h_f$ but also at rest. So, basically, you only changed the vertical position of the object, but you didn't do anything else. The second important thing is a property of the gravitational field, technically summarized in the statement which says that the gravitational field is conservative. This means that if you move an object from a position to another one in the presence of the gravitational field, the work you need to do will only depend on those positions, and not on the path you take to move your object. Compare this with my first sentence (in general, work depends on how you do it): it is a particular property of the gravitational field (and other important fields like the electric one) the non-dependence of the work on the path you take. And, in saying this, we are also assuming that the object you move is at rest both at the initial and final positions. These two things allow you to write the previous equation for the work $W$.
Now, to give you some more physical insight, how can you understand all these ideas with the definition $W = F d$ for work (where $F$ is a constant force and $d$ the distance you move an object in the presence of that force)? Well, if we are going to lift an object from a height $h_i$ to another height $h_f$ so that $d=h_f - h_i$, we will have to apply some force $F$. But, as we said before, we need to start at rest and we also need to finish at rest, so this force $F$ has to be really close to the gravitational force the object suffers (its weight), because otherwise we will have an acceleration and at the final point our body will be moving with a certain velocity. Suppose we take then $F = Mg + \Delta F$, with $\Delta F > 0$ really small. The work done when lifting the object is:
$$ W = (Mg + \Delta F) (h_f - h_i) $$
The extra force $\Delta F$ will cause a small acceleration upwards which will produce a non-zero final velocity, but this velocicty can be made as small as you want by taking $\Delta F$ smaller and smaller. In the limit, we have to apply a force exactly equal to the weight of the object to raise it without producing a final velocity, so in this situation the work would be $W = M g (h_f - h_i)$, which is the same equation we had before when we were thinking in terms of the gravitational potential energy. But hopefully this time you will have a little bit more physical insight in what is exactly going on here.
