Suppose that energy is conserved in one frame of reference, and you want it to be conserved in all other frames as well. Conservation of momentum is exactly the condition you need in order to make this happen in all frames.
To see this, consider what happens when you change to a different frame of reference, $v\rightarrow v+u$. Then all kinetic energies transform according to $K\rightarrow K+muv+\text{const.}$ (Potential energies don't change under this transformation.)
Let's say we write your question as a conjecture: --
If energy is conserved and total KE is conserved, then momentum is conserved.
Then your conjecture can actually be strengthened to read: --
If energy is conserved, then momentum is conserved.
(This is implicitly assuming that we want all frames of reference to be valid.)