Much of the discussion has been around the idea that 'given that there weren't really any 'mercenaries' as such in the late Victorian period, what's the closest parallel to the notion?' - and I think as non-nationals fighting for a state, organised into a regiment, that the Foreign Legion is the closest, as well as having a fairly distinctive uniform.
But in the end the justification will have to come from the fluff - whether that's 'x-power, which recruited the aliens first, gave them these uniforms' or 'they're currently fighting for y-power so they're wearing these uniforms' or 'the first humans they defeated were from z-power and the aliens looted these uniforms from them', or whatever.