The easiest way to answer this is:
MOST of the time, when you short a stock, the broker is loaning you shares held by the brokerage in their own accounts, and since they're charging you a fee to borrow the shares, they make money on stock they can still resell to someone else later once you cover the short position. This can be very lucrative for the broker.
Don't forget that when you hold a short position, the brokerage is going to continue assessing a fee for the duration of the short - it isn't necessarily a one-time fee. If you hold a short position beyond the end of the month, for instance, the brokerage might charge you another fee to continue the position into the new month, which obviously deducts from your anticipated profits when covering.
By the way, just because you're shorting a stock doesn't mean you're selling it to someone else. You're borrowing shares you don't own, or more precisely, the VALUE of those shares at the time the short position is created. What you're anticipating with the short is that the stock's price will fall and you can then "buy" the shares back at the lower price, pocketing the difference (minus fees) as profit.