The terms pair of scissors and pair of pants both refer to single objects that are, in normal use, never separated into the components that make them nominally a pair. When these terms are modified, they are modified as a whole — effectively a new pair-of-pants or new pair-of-scissors.
Shoes existsexist singly as well as in pairs (though notrarely used much that wayindividually). Did you see my other shoe? (But not, Did you see my other ∗scissor?) As such, the pair of shoes phrase is not locked as one.
I fully agree with other answers that new pair of shoes is more common than pair of new shoes. However, the latter is logical and correct, even though it is probably not the preferred form.