What's the deal with "legacy" and "segwit" wallets?
Later I read that it's impossible to transfer bitcoin between those two kinds of wallets. Is it true?

This is not true.
However a wallet needs to know about Segwit addresses in order to be able to send to them. Since it is a new address type (well new when it was introduced 3 years ago), software that hasn't implemented it yet won't know what to do with it.

I tried this kind of transfer (legacy -&gt; segwit) using Electrum and it didn't work. Does software matter?

In what way did it not work? Electrum supports and uses segwit, so it should, unless you are using an older version of Electrum. Both the software and version of that software do matter.