[Suicide Junkie]

I think the engines would be represented as horses, wagons or whatever transportation you're using.

Give the ship a +1 standard movement built into the hull to represent basic marching.

Each component soldier can be given a movement bonus ability. The slowest soldier will then determine the army's speed.