Who are Faceless Men?
The Faceless men serve The Many Faced God. Their belief is that all men are right about Gods but no matter what they call their God, he is actually the one with many faces, who shall welcome every man at the end of his days. So basically their belief is that Yitish god Lion of Night, Westerosi god The Stranger, Black Goat of Qohor are all the different names of one God, him of the many faces.
The tale of TFLM's beginnings centers around a figure of unknown origins who was the first Faceless Man. This man heard the prayers of the slaves to their various gods and came to conclude that they all prayed to the same god "with a hundred different faces", the Many-Faced God, and that he was "that god's instrument". This led to him giving "the first gift" to the most desperate slave.
By this account we can estimate date for establishment of the Facelessmen order to the Rise of Valyrian Freehold. However we do know that the Long Night was long time before Valyrians rose with their dragons. Long Night was about 8000 years before the conquest and
while we do not know when did Valyrian Freehold establish itself, Valyrian freehold established itself 5000 years before the conquest and we do know that it reached zenith of its power in about 950 years before Conquest when they fought in Rhoynish wars. Therefore the order can't be the soldiers of the Great other because Valyria was formed 3,000 years after Long Night and FLM were formed even after that.
Also Faceless men do not kill for their own desire or for fun (or for a secret genocidal mission) which is what Arya Stark is having a hard time to understand.
Are they soldiers of The Great Other?
When Melisandre makes this statement:
Death is his domain, the dead his soldiers.
She is not referring to The Faceless men.
Faceless men are most certainly not dead and thus do not qualify for being soldiers of the great Other. Also while they do have death as their domain, they grant it as a gift, not out of hatred for everything with warm blood as Wights and others do.
AWOIAF Wiki defines Wights as:
Wights are dead men or creatures raised up by the Others, seemingly
when touched by the cold that accompanies them.
Those are your dead soldiers.
The Others themselves however are not dead. As George R.R. Martin said:
The Others are not dead. They are strange, beautiful… think, oh… the
Sidhe made of ice, something like that… a different sort of life…
inhuman, elegant, dangerous.
- Order did not exist during the time of the Long Night which was 8000 years before Aegon's Conquest of Westeros. Order was founded during reign of the Valyrian Freehold which was few thousand years after the long Night.
- The members of the order are not dead and thus Wights fit Mel's description in a better way. If Mel suspected that, she would not have crossed the narrow sea to fight the war for light, she would have gone to Braavos which was more convenient to her.
- Order does not kill people for their own desire or just for the sake of it. Nor do they do it out of hatred or enchantment. They do it as a mercy and a gift.
- They worship the many faced god who is supposed to be the same god as Lion of the Night. According to Yi-Tish legend about the Long Night, it was caused by Blood betrayal and thus Lion of the Night brought death and darkness to the world. Why worship a god associated with such an act unless you feel affinity towards his deeds? But that in itself is a weak argument because then we should also assume that Tyrion is also hands in glove with the others because he lighted a candle to Stranger (Also supposed to be same as MFG) before Battle of the Blackwater.
Ancient Five Forts of Yi-Ti are built to keep Lion of the Night
away from realms of the Men much like the Wall is raised in Westeros
to keep the others away. The Walls of those forts are fused black
stone which makes one think they are Valyrian however they predate
the Valyrian freehold.