When an exchange sends payments, they send them in bulk.  They send one transaction with several outputs.

The size for a typical Bitcoin transaction with one input and one output is about 226 bytes.  Transaction fees are based on the number of bytes that your transaction takes up on the blockchain (what you're basically paying for is space on the blockchain).

IIRC, each output only adds 34 bytes to the transaction, so if an exchange sends to many people at once, the transaction fee decreases relative to the number of people that they're sending to.