After a bit of Googling, it seems like the origin is one of two Pidgin English dialects: Chinese/English and Native American/English. It sounds credible to me.
Many Chinese workers immigrated to the US in the mid 1800's to work on the first transcontinental railroad. Pidins developed as a result, and some of the common expressions became set phrases. At the same time, Native Americans developed a pidgin, too.
Some of the pidgin language was (fallaciously?) mimicked in the Lone Ranger and Tarzan TV series and early talkies - Western, Tarzan, Charlie Chan and other films, and so entered the mainstream.