There's a few traits that are key here:
1) You need to handpick the leadership
Whomever you pick to lead this outfit has to have impeccable military credentials, and be able to establish him/her self as someone worthy of being followed by the soldiers you will recruit later.
Essentially, you need someone who is such a barely restrained psychotic killer that even the most rabid of men your foreign legion is likely to attract would dare question their authority.
If this person also has an incredible (if somewhat tarnished) military career, all the better.
The rest of your cadre will similarly need to be incredibly battle hardened and ruthless individuals.
2) You need to offer new identities
A big incentive to join The Legion is that once you do, you essentially disappear. A wanted murderer, war criminal, or rebel leader is such no more. All are faceless, non-identifiable drones in this unit.
Those joining need to be able to trust that once accepted within those ranks, you will never betray them - unless they make you question their loyalty.
3) You need to operate in utter secrecy
Everyone knows you exist, and everyone may even know who leads the Legion, but no one - and I mean no one - may know the identities of the soldiers within the ranks.
Their military structure is completely separate from that of the regular forces. They answer to no leaders except their own, or you. Furthermore, any disciplinary action can only be taken within their own circle (and should typically be summary execution, because you'll be dealing with some real works of art)
4) You don't get to be picky
You will accept practically anyone who present himself on your doorstep. Murderers, rapists, hooligans, or trained professionals. Give enemy combatants a chance to join up.
However, by the end of the training process they will either be willing tools of destruction, bending to your will, or dead. Let the myth build that anyone who joins, no matter how desperate, is accepted. The truth that most are probably killed in the training will never filter out.
This way you do not discourage anyone from applying, but you do weed out any elements that are just too chaotic. Someone who takes to killing their fellow soldiers because they have no one else to hunt down at the moment should be identified and put down.
5) Build esprit de corps
This unit should not only be highly trained, but also very well equipped. Those who successfully pass the brutal training should have an intense sense of pride instilled into them.
They are the best, of the best, of the best. The second best guys? The Legion killed them, and they know it.
6) Reward them well, and promise more to come
This is not a regular army unit. They are essentially mercenaries bound to you by desperation. In this relationship you hold all the cards (the keys to their former identities, as well as their future one).
Very few of them will achieve "freedom". In fact, most of them will willingly stick around for the killing, and perks - which should be lavish, when possible, to compensate for the insane work conditions they endure the other 90% of the time. Those who do fulfill their contract (10 - 15 yrs of service) should, however, be honorably dealt with.
They should be aware that they need to keep their mouths shut, and will be monitored for the rest of their lives, but word will also spread in the ranks that you keep your word, and there exists a light at the end of the tunnel. This will serve to command loyalty.