I suppose with any form of credit/debt, you can create a market with more shares than actually exist. You're selling the promise of shares.
The only other thing I can think of is that instead of trading the actual (or virtual) shares, the parties in the contract are trading a new instrument who's value is tied to the share being shorted.
In other cases, especially retail accounts, the shares are really being held in trust by the brokerage so they're not actually necessarily being moved, it's more of a pool where you have a specific claim on that pool based on the value of the assets in your account. (This is in fact where the "borrow" on a stock may come from - that same brokerage may be lending shares from that pool to people who want to short a stock - generally you can tell the brokerage not to lend your shares out to those shorting.)
The classic short squeeze example, by the way, is the recent Porsche / VW short squeeze where Porsche essentially screwed shorts by buying up so much of VW that there was only 6% of stock left in "float" while there was 12.1% of the company on loan to shorts. All of a sudden there were 2 shares of shorted stock for every 1 not owned by Porsche, and they could pretty much dictate whatever price they wanted to shorts desperate to close out their positions. Totally fair, very funny.