I think you need to stop thinking of it as a wallet. We refer to bitcoin addresses as wallets because it's a simple analogy that helps people understand their practical use (i.e. there is money stored in it that you can spend).

However, your question illuminates the flaw with that nomenclature. It is actually a ledger. The ledger contains all of the addresses and transactions on the bitcoin network. You don't really own the bitcoins as much as you own the unique ability to send them to another address (by controlling the private key).

The tx fee is essentially a bribe to have the miner that wins that block to include your transaction in the new block. They are also awarded the freshly minted bitcoin, but your fees aren't being re-mined; they're just paying for their service to include that transaction in the block.