But first up, the obvious Biblical parallel! That's part of what makes them so suspicious. But the army was Taim's (or Demandred's) idea in the first place, and Taim has aggressively been trying to recruit Darkfriends. We know he was only able to control so much of recruiting without giving himself away, but that still gave him plenty of opportunity to recruit among Darkfriends for channelers and soldiers (particularly officer material) at the same time. And then, on top of that, they took in Sammael's apparently most loyal troops in Illian, the leader of which tried to kill Rand.

All of this was developed in TPOD, the same book where Roedred was being developed under our unsuspecting noses. (And under Rand's unsuspecting nose, which is the point of hiding out in Murandy of all places, where no one will ever think to find the Shadow's Great Captain. In Lugard, the Sin City of Randland.) The Shadow was all around Rand in TPOD—by his side, in his head, and across the field of battle in Altara and again in Cairhien—and it was strong around the girls as well. It was perhaps the darkest book in the series, and the kidnapping of Faile was the least of it. But Bashere's 'something dark' might well be related to the Legion. It doesn't have to be, but he is their commander, and the Legion is well-positioned to take him out when the time comes. Demandred might be planning to take out all of their Great Captains at once (including Mat, not that he will be successful).