Image that a photon is emitted from a sphere, moving orthogonally away from the sphere's surface. As the weight of this sphere increased, how would the increasing gravitational force affect the motion of the photon? Imagine that the mass of the sphere was sufficiently high to form a black hole - but the photon is emitted outside the black hole's event horizon - what happens to the photon then?
Photon momentum does not correspond to its velocity, but its frequency, so if you applied a force opposite to its momentum, it would not slow down, but redshift.
As photons carry no charge, the only force applicable is gravity, and its general relativistic description is more kinematical than dynamical (the photon gets redshifted because the relative orientation of the velocity vectors of photon and observer changed while moving along a straight line through curved spacetime - no forces anywhere in sight).
As to where the energy goes, the classical answer is into the gravitational potential. The relativistic answer is a bit more complicated as it's not possible to associate an energy density with the gravitational field. Morally speaking, it's arguably nevertheless the right idea.