Change in momentum is force times time. On the other hand, change in kinetic energy is force times distance (more accurately, the component of the force along the movement times distance; a force perpendicular to the movement doesn't change the energy).
Now imagine you apply a force for a given time to an object initially at rest. The momentum will grow by the product of the force and the time. Since the object will have moved a certain distance after that time (and certainly in the direction of the force), its energy will also have increased by a certain amount. Also since a constant force means a constant acceleration, the velocity will also have increased by a certain amount.
Now imagine that you apply the same force for another second. For the momentum it's simple: The product of force and time is, of course, the same again, and therefore the momentum has grown by the same amount. Similarly, the acceleration was the same, and therefore the velocity has grown by the same amount. It is also easy to check that the same applies for a third acceleration phase, a fourth acceleration phase, and so on. Thus the growth of velocity and the growth of momentum are proportional.
On the other hand, if we look at the change of energy, we see that for the second acceleration, we get a greater energy growth, as the object was already moving, and therefore the total covered distance is larger.
So how much larger is the energy growth? Well, since the force was the same, it is the same as the difference of the covered distance. Now we had a constant force, and therefore uniform acceleration, which means the average velocity during the acceleration is just the arithmetic mean between the initial and final velocity.
So if we denote the final velocity of the first acceleration with $v$, then, because the initial velocity was zero, the average velocity during the first acceleration phase was $(0+v)/2=v/2$, and therefore the covered distance was $vt/2$, where $t$ is the time of acceleration.
On the other hand, the average velocity of the second acceleration phase is $(v+2v)/2 = 3v/2$, and thus the covered distance is $3vt/2$, o three times the distance of the first acceleration phase. Thus the total change of energy (and thus the total kinetic energy, since we started out with an object at rest, thus without any kinetic energy) is four times the kinetic energy after the first acceleration. Thus at twice the speed we have four times the kinetic energy.
If we do a third acceleration phase, the average now is $(2v+3v)/2 = 5v/2$, thus the kinetic energy at three times the speed gets a factor $1+3+5 = 9 = 3^2$. Similarly, at four times the speed, the kinetic energy gets a factor $1+3+5+7=16=4^2$. So we see that the kinetic energy goes with the square of the velocity.
This is related to the fact that the covered distance of an uniformly accelerated object is proportional to the square of the time of acceleration. Indeed, with constant force starting from rest, velocity is proportional to time, while covered distance is proportional to the square of time, thus covered distance (and therefore kinetic energy) is proportional to the square of velocity.