Short order is a legal term in English law. From Pleading and Practice of the High Court of Chancery by Edmund Robert Daniell, FRS (first American edition, 1846):
In other cases a practice existed of obtaining what was called a short order; that is, an order requiring the performance of the particular part of the decree which it was intended to enforce, within a specified period, and then, upon default made in compliance with the terms of that order, enforcing the performace of it by a writ of execution commanding obedience to that order only.
A short order of this nature was necessary in all cases, (except a simple direction for payment of money to a party,) in which it was intended to enforce the immediate performance of one or more parts of a decree: therefore, wherever it was wished to enforce the transfer of stock in the public funds, or the performance of any other act directed by the decree, it was necessary, in the first instance, to procure a short order directing it to be done on or before a certain day.
Emphasis mine; many thanks to @mgkrebbs for the definition.
I find it as early as the decision in Hinton versus Hinton, July 16, 1755 (and I'm sure it was already a well-known phrase):
...but in neither of these places is there in the register's book any state of the pleadings or case; in the latter place is a common short order of dismission; so that no state and no light can be had from thence.
Here's a modern example of a short order (in the original sense) declaring Pakistan's National Reconciliation Order of 2007 unconstitutional:
Thus, it violates various provisions of the Constitution. Therefore, by means of instant short order, reasons of which shall be recorded later, we hold as follows:-
Clearly, the legal sense of "short order" is that the order of the court shall be carried out immediately, or consequences will follow. I'm not saying that that's the origin of "in short order", but I think it lays the groundwork.
The first place I find "short order" used in the current sense is in a passage from a letter to the editor of the Atlantic magazine dated April 12th, 1824:
I have not, indeed, heard from or of you, since that memorable day, when I packed up my alls, and marched off at short order, without beat of drum, or asking what was to pay...
The first place I find "in short order" is in the "Journal of a Traveller to Louisville" in the American Farmer, dated Jan. 8, 1826:
The gentlemen continued patient until the ruffian had sufficiently amused himself, and was several miles on his journey, and then putting the spur to their horses they soon overtook him, and at the end of the end of the lash, compelled him to return, and in the language of the driver "made a Baptist of him in short order."
In Hotel Meat Cooking by Jessup Whitehead (seventh edition, 1901), we see:
The short order cook has the middle of the table and the middle of the range for cooking eggs and omelets, frying breaded articles, and perhaps he has the potatoes and onions, fried mush and tripe in batter, and the like.
O. Henry's first use of the phrase is in the short story An Adjustment of Nature, from the collection The Four Million:
There amid the steam of vegetables and the vapours of acres of "ham and," the crash of crockery, the clatter of steel, the screaming of "short orders," the cries of the hungering and all the horrid tumult of feeding man, surrounded by swarms of the buzzing winged beasts bequeathed us by Pharaoh, Milly steered her magnificent way like some great liner cleaving among the canoes of howling savages.