Well, if you wanted to just stamp your feet and have an army pop up, its not all that hard.
If the US were to announce that they were recruiting an Army corps of Filipinos you would have half the Philippine military (and mostly the best half) in line to volunteer. You could put together a couple of very decent light infantry divisions in a few weeks, out of the manpower of the Philippine equivalent of 10-12 (understrength) divisions. It would be useful to have a single nation and military as the source, as they will be from a single culture and will already have been trained in a compatible system, whatever its faults.
The Philippine government may not be too happy though. I guess if you went gradually and traded the men for military aid.
If you wanted a real Foreign Legion there are far more than 25K trained experienced soldiers from respectable militaries available around the world.
The source of direction and authority is the real killer here as you say.
Which brings us back to the beginning since it wouldn't be a mercenary army, it would be an American force, regardless of it's name.