How do exchanges provide wallets unique wallets to users but also keep transaction fees low?
Users don't have addresses at exchanges. When you deposit to the exchange you're depositing to the exchanges wallet, with a unique address just enabling them to account for who to credit the internal balance to. Withdraws only require one on chain transaction, just debiting the amount from the database and then sending that value to the address requested.