Create a flat Lattice and Shrinkwrap it to your terrain. Make sure it has enough divisions to conform to the terrain accurately.
The reason for using a Lattice is that directly Shrink-wrapping a mesh against another mesh when animating will create jittery snapping artifacts as verts latch on to other verts, while a Lattice on the other hand smoothly interprets the curve and makes it usable via the Lattice Modifier.
Create a particle emitter plane and put a Lattice Modifier on it that uses that Lattice.
Animate the emitter plane traveling across the Lattice.
The original animated characters must be on an enabled layer or their animation will not be calculated for their particles.


With just one character model used, the marching looks too uniform. But this can be remedied by using a group instead and having each model in the group have variation in physical appearance and walk cycle.
There's just one more issue to address. You may have noticed some of the troops are scaling the steep hills too quickly. Others have limbs intersecting with one another. These problems can be fixed by using shape keys to deform the vertex positions of the emitter mesh to steer troops away from obstacles:

An alternative to using Shape Keys is to Hook an Empty to their emitter vertex and control them using that. The Empty will need to be parented to the emitter mesh to move in relation to it.

Note that these techniques require the particles to be set to emit from verts, not faces.