Imagine a car crash. A car coming at a high speed has a head on collision with a car at rest. When the car makes impact, it will move the other car with it at a slower speed then it was travelling at. In this case, the velocity decreased since the car slowed down, but the mass increased since there are now two cars moving. Momentum was conserved because the change in mass accounts for the loss of velocity.