The 2 other examples are Спасибо which can be traced to Спаси Бог (г dropped out eventually), and здравствуйте which literally means 'будьте в здравии, в здоровье, be well, be in health' but is perceived as just 'hello, hi' in modern language.
Deb, прощай traditionally implies people are not supposed to see each other again. It's quite a literary word, for sutuations like:
Прощайте, братцы! Не поминайте лихом! Не увидимся уж боле! or
Прощай, душа моя. Расстанемся навеки. Прощайте эти милые леса и реки! - he is leaving the country and his beloved one.
Such words are connected with the Russian Orthodox aspect of Russia, forgiveness being one of the cornerstones or the Russian Orthodox tradition.
Today we tend to often say Не прощаемся , which means we hope to meet again in the future.