Hay múltiples maneras de ver esto.
Lo más sencillo, creo, es que la energía cinética escala con el cuadrado de la velocidad $$K=\frac 12 m v^2$$
Si suponemos que el cohete propulsor proporciona una aceleración constante, al comparar las velocidades inicial y final encontramos que $$\Delta v=v_\text{final}-v_\text{init}=at$$
Así que para la misma cantidad de tiempo, el cambio en la velocidad es el mismo, independientemente de cuál sea la velocidad inicial. Como tenemos una dependencia al cuadrado de la velocidad en $K$ Esto significa que la energía cinética aumenta más si empezamos con una velocidad mayor. $$\Delta K=\frac 12 m v_\text{final}^2-\frac 12 m v_\text{init}^2=\frac 12 m (v_\text{final}-v_\text{init})(v_\text{final}+v_\text{init})=\frac 12 m\, \Delta v (\Delta v+2v_\text{init})$$
Así que, como podemos ver, la suma de las velocidades en la expresión para $\Delta K$ es lo que contribuye a un mayor cambio en la energía cinética. Como el trabajo realizado es igual al cambio de energía cinética, debe ser que el cohete hace más trabajo cuando partimos a una velocidad mayor.
La segunda forma de ver esto, que podría argumentar que es la misma que la primera, es mirar la definición de trabajo $$W=\int\vec F \cdot \mathrm d\vec x$$
O en una dimensión con una fuerza constante $$W=F\,\Delta x$$
Ahora, suponiendo de nuevo una aceleración constante, sabemos que $$\Delta x = \frac 12 a t^2 + v_\text{init}t$$
Para que el trabajo realizado sea $$W=F\left(\frac 12 a t^2 + v_\text{init}t\right)$$
Una vez más, vemos que la velocidad inicial determina el trabajo. Una explicación cualitativa de esto es que cuando la velocidad es mayor, entonces el objeto cubre más distancia en la misma cantidad de tiempo. Por lo tanto, si observamos el tiempo en que se aplica la fuerza, cuanto más rápido se mueve, mayor es la distancia que se aplica. Por lo tanto, obtenemos más trabajo si el objeto se mueve inicialmente más rápido.
El supuesto problema detrás de todo esto es que parece que estamos obteniendo más energía al aplicar la misma fuerza durante el mismo tiempo. Pero si se trabaja en ello, se descubre que no es un problema en absoluto. Esto es incluso cierto para los objetos que caen cerca de la superficie de la Tierra. Aunque la fuerza sea constante, la gravedad hace cada vez más trabajo sobre el objeto mientras cae. O, en otras palabras, la tasa de conversión de energía potencial en energía cinética aumenta a medida que el objeto cae.