The market cap is the sticker price - how much it will cost to buy all the shares.
The cash the company has on hand is like a mail-in-rebate. After you've bought the company, you'll get that cash back, so you consider that rebate value against the sticker price when evaluating the price you're actually going to have to pay.
Debt is like an extra cost you also have to take on when you purchase the company - like a delivery charge. So you need to add that on to the sticker price to evaluate the true cost.
Since the true price is market cap + debt - cash, and the debt and cash are somewhat fixed, it should come as no surprise that the market cap, via the share price, adjusts itself such that the true price reflects the company's value more accurately than the market cap does.
So it's the other way round: the more debt a company of a given value has, the lower its market cap will be. Which makes more sense.