They say the wallet is stored on the blockchain. When you create a wallet, there are no fees. Who pays for this?
Whoever said that has a misunderstanding of what a wallet is. Wallets are not stored on the blockchain, they are stored on your local machine or with the service you are using. In the case of electrum (you posted in the electrum sub after all) the wallet file is stored on your local machine.
You can recover your wallet from the 12 word seed. If you have nothing, you can retrieve your wallet from the 12 word seed. When you receive this wallet there is no password on it. It is all instantaneous, thus how can it be on the blockchain if there is no fee?
If you create a electrum wallet, send 5 bitcoins to it. Send 2 btc to someone, then delete the wallet. You can then retreive your wallet immediately on another computer.
To try to make the question more clear say you have a fresh install of windows. You download electrum and retrieve your wallet with 12 words. Suppose you have 100s of transactions. Where did you wallet retrieve from? It can't be bitcoin blockchain since no fees were paid and it is all instantaneous. You might have retrieved 1000 bytes of info from 60 bytes of words.