> The previous answers all restate the problem as "Work is force dot/times distance". But this is not really satisfying, because you could then ask "Why is work force dot distance?" and the mystery is the same.

...

> But now look at this in a train which is moving along with one of the balls before the collision. In this frame of reference, the first ball starts out stopped, the second ball hits it at 2v, and the two-ball stuck system ends up moving with velocity v.

That's still just pushing the problem elsewhere. Intuitively, why does the two-ball system end up with a velocity of 1v?