I will promote my comment to an answer. The theory of permutations and permutation groups was the original (abstract) setting of group theory, and so the term originated there. I believe the reason for it was as follows:
The order of a permutation is the least number such that the ordering of the index set is preserved.
I looked in both Lagrange's 1771 memoir and Cauchy's 1844 memoir, which both address Lagrange's theorem on orders of subgroups. Lagrange barely uses the word order (well, "ordre" as he is writing in French), and doesn't use it in a way which influences out discussion here (the only relevant use is on p201, when he changes the orders of variables in an equation).
Cauchy's memoir is more relevant. He goes from talking about, basically, "permutations change the order of the index set" to defining the order of a permutation. He doesn't justify this name, but writing like this does suggest the reason is that it is the least number such that the ordering of the index set is preserved, as per my claim above.