I've read through this thread but I'm surprised not to hear more mention of gravitational waves.
Gravitational waves are are the simple answer to the OP's question. (at least according to my high-energy physics textbook). [Edit: I mis-read or mis-remembered what I studied. Corrections made below after double checking.]
Even ignoring baryonic matter for the moment, assuming there are some slight fluctuations in dark matter density in the early universe (i.e., nearly uniform, but not quite), clumps of dark matter would collapse on themselves. But similar to how
@haruspex has already mentioned, if our universe obeyed Newtonian gravity, those clumps would merely oscillate indefinitely, getting smaller then bigger, then smaller again and bigger again, and so on and so on, without end. Where did the energy go?
Gravitational waves. A galaxy or even galaxy cluster sized [in terms of mass] chunk of dark matter would produce jaw dropping amounts of gravitational waves from the oscillations as it collapsed and oscillated. These gravitational waves radiate away from the center leaving less energy in the system than when it started.
[Edit: The chaotically varying gravitational field adds an additional heating component to the baryonic matter besides that of the adiabatic heating. That heat is then released by the baryonic matter in the form of photons.]
Eventually the oscillations die out when the system becomes virial, and the
shape of the clump becomes stable over time. Dark matter particles (assuming WIMPs) have greatly varying speeds relative to each other, but on large scales, the shape of the ensemble remains constant. Since the shape of the clump is now constant, you no longer get appreciable gravitational wave generation.
Add that tiny bit of baryonic matter into the mix, and it doesn't change a whole lot. The baryonic matter just goes along for the ride.
The interesting question is whether the supermassive black holes at the center of galaxies simply came from the mergers of many stellar sized black holes or if the galaxy's initial collapse and oscillations (before virialization) played a more significant role. I don't know enough about the subject to comment on that, so I'll end it there. (It's not really part of the OP's question anyway).
But for a simple answer,
haruspex said:
That doesn't explain the loss of energy. If the dark matter started (roughly) uniformly spread over the vastness of space, the KE when trapped in orbit in a galaxy is only half the lost PE. Where did the rest go?
you needn't look any further than
gravitational waves heating of the baryionic matter within a chaotically changing gravitational field. They [photons] carried the energy away.