1. perhaps from a German idiom "adieu so lange"
(compare German parting salutation "adieu so lange", the full sense of which probably is something like "farewell, whilst we're apart");
most etymology sources seem to lean toward the German origin.
2. or perhaps from Hebrew "shalom" (via Yiddish "sholom");
3. Some have noted a similarity to Scandinavian leave-taking phrases, such as:
3a. Norwegian "Adjø så lenge", "Farvel så lenge", "Mor'n så lenge", literally "bye so long, farewell so long, morning so long";
3b. and Swedish "Hej så länge" = "good-bye for now", with "så länge" = "for now" attested since 1850, according to Swedish sources.
4. Earlier guesses that it was a sailors' corruption of a South Pacific form of Arabic "salaam" are not now regarded as convincing.
5. "Dictionary of American Slang" also adds to the list of candidates Irish "slán" = "safe", said to be used as a salutation in parting.
The phrase seems to have turned up simultaneously in America, Britain, and perhaps Canada, originally among lower classes.
First attested use is in title and text of the last poem in Whitman's "Leaves of Grass" in the 1860 edition:
An unknown sphere, more real than I dream'd, more direct, darts awakening rays about me -- So long!
Remember my words -- I may again return,
I love you -- I depart from materials;
I am as one disembodied, triumphant, dead.
Whitman's friend and fan William Sloane Kennedy wrote in 1923:
The salutation of parting -- 'So long!' -- was, I believe, until recent years, unintelligible to the majority of persons in America, especially in the interior, and to members of the middle and professional classes. I had never heard of it until I read it in Leaves of Grass, but since then have quite often heard it used by the laboring class and other classes in New England cities. Walt wrote to me, defining 'so long' thus: "A salutation of departure, greatly used among sailors, sports, & prostitutes -- the sense of it is 'Till we meet again,' -- conveying an inference that somehow they will doubtless so meet, sooner or later." ...
It is evidently about equivalent to our 'See you later.' The phrase is reported as used by farm laborers near Banff, Scotland. In Canada it is frequently heard; 'and its use is not entirely confined to the vulgar.' It is in common use among the working classes of Liverpool and among sailors at Newcastle-upon-Tyne, and in Dorsetshire. ...
The London Globe suggests that the expression is derived from the Norwegian 'Saa laenge,' a common form of 'farewell,' au revoir. If so, the phrase was picked up from the Norwegians in America, where 'So long' first was heard. The expression is now (1923) often used by the literary and artistic classes."