As you say, many idioms of that form (like "make one's way", "cut one's way", etc.) use a transitive verb with "way" as its direct object.
The ones that use an apparently intransitive verb, (work, shop, jog[?], etc.) are understood by analogy with the others that have transitive verbs.
I have heard people say "I made my way across town", so if I went window-shopping, I might say, using the same pattern, "I window-shopped my way across town." Of course "to window-shop" doesn't normally take a direct object. It is an intransitive verb. But in this case, I have used it as if it were a transitive verb with "way" is its direct object.
It is a fanciful extrapolation of grammar. "Walk" is usually intransitive, but if "you walk your dog," "dog" is the direct object of "walk". "Swim" doesn't usually take an object, but if a mermaid had a pet fish, she might put its little leash on it, and say, "I'm going to swim my fish," and we would know what she meant because of the pattern of dog walking.
So in your examples,
He worked his way through the book.
They shopped their way around New York.
"worked" and "shopped" are used as transitive verbs. And yes, "his way" and "their way" are objects.