When exchanging coins you HAVE to put all your coins in a pool with other people and get "credit" of amount, this is so you can transfer ownership of the coins in exchange for ownership of other coins. (It's also the reason when an exchange gets hacked every body are screwed)

So all exchanges must have a wallet with all funds in one shared pool right? (shapeshift connects to existing exchanges)

Apart for the typical client wallet where you own your keys there are also hybrid wallets where the user controls the keys like coinomi or coinvault.io (for alt coins) the wallet service will normally advertise that.