What Dimitrios Tolios said. Those who think it sounds like ¡Adios! are right: it’s from Italian Addio.
Add έχε γεια “have health = farewell” as the now decidedly archaic antecedent of γεια σου.
When you are the one staying behind, the traditional response is στο καλό “to the good = God speed”