As we know the gravitational potential is the work done per unit mass in taking a point mass from zero potential (at infinity distance) to a point in a gravitational field. But why is the work negative and hence the gravitational potential have negative values?
In this case it's because of who's doing the work. The derivation you cite regards the work as being done by the gravitational field. This means in bringing the object from infinity, the gravitational field has lost that energy to the object. Conversely, the work done on the object is the positive value.
Everything else works out and when we take the negative gradient to obtain the force/acceleration, we obtain a negative quantity again meaning our gravitational field is attractive to mass and accelerations vectors point further towards the depths of the potential.
Similar arguments are commonly wrought for work done by something on something else in electrodynamics and thermodynamics as well.