ETA: got interrupted halfway through and the real physicists beat me to actually posting. Oh well, I typed it so you’re stuck looking at it. 
Gotta be careful about combining “faster /slower” which is about speed with “velocity” which is about speed and direction.
@Chronos did a fine job in very few words, but maybe a little too abstract for you. The three experts just above me also did a fine job, but may lack the context for you to slot their good info in where it belongs.
Lemme try this, taking it in smaller more explicit bites.
Let’s call the direction the two bodies are traveling as North. They start out both going North at the same speed on parallel tracks some specific distance apart.
Once we let them go, gravity begins pulling them towards each other. The one to the west is pulled exactly east by the gravity of the other. And vice versa. The one to the east is pulled exactly west by the gravity of the first one.
100% of the gravity force is east/west and zero of it is north/south. So the speed in the northerly direction remains exactly the same. While meanwhile the speed of the western one moving east and of the eastern one moving west keeps increasing over time. So the longer time goes by the faster they’re going east/westward. Their total speed in a northeasterly or northwesterly direction is increasing because it’s the vector sum of the unchanging northerly speed and the increasing east- and west-bound speeds of the two bodies.
And the closer they get together, the stronger the mutual gravity gets, so they accelerate towards each other at an increasing rate. But still, 100% of this acceleration is east/west and is having zero effect on their absolutely constant speed northward.
As time goes on they keep getting closer and closer and moving faster and faster east/westward. With their still unchanging northward speed. The vector sum of those speeds, their velocity, is increasing. And is aimed more and more easterly/westerly as that component of velocity continuously gets bigger while the northerly component is unchanged.
At the moment just before they touch, the western one is moving east at some speed X. And the eastern one is moving west at the exact same speed X, just in the opposite direction. While both are also going north at the original unchanging speed.
Eventually they crunch together. And per your assumptions stick together in a single bigger lump. At that moment the easterly speed and westerly speed combine to zero. The northerly speed remains unchanged. And so the vector sum of zero east/west and the unchanged northerly speed is exactly the same as when the experiment started. Same direction (north) and same magnitude of speed. So same velocity as at the start. But a different direction and a different magnitude = speed from the moment before they collided.
What happened to the kinetic energy of their east/west motion? It was converted to heat as they smooshed and stuck together. Where did that kinetic energy come from originally? From the potential energy that was two gravitating bodies held some distance apart just before we let the experiment begin.