Why does a bijection from a set to itself deserve the name "Permutation"?

"Rearranging" objects is a procedure that is not inherently related with order. The relation with order is more due to how we usually list things than the essence of permutation itself.

For instance, I have three pockets in my pants, on which I put my cell phone, keys and wallet, one on each pocket. I sometimes rearrange them; driving with the wallet on the right pocket of some pants is somewhat unpleasant. I think it is natural to call this process of changing from one alocation to another a permutation, and I think people would generally agree. This is precisely a function $f: Pockets \to Pockets$ which tells me that whatever was in pocket $x$ is now in pocket $f(x)$. Note that I never made any ordering of the pockets.

As I mentioned in the introduction, I think you are assuming that an ordering must be given due to the same reason why I said "cell phone, keys and wallet": because this is how we are used to communicate things, by listing them.

"A bijective map from a set to itself" does not require the set to be ordered, but when applied to an ordered set, this map acts to reorder the set.

This definition is therefore a generalization of the idea of "reordering an ordered set" to a more general setting.

Often, in mathematics, a name lifts with a generalization.