Can legacy wallets with 1xxx addresses send to segwit 3xxx and bc1xxx addresses like mycellium that only does 1xxx addresses? I have mycellium for android and currently they dont support any segwit addresses that has 3xxx or bc1xxx. Can I send out from my mycellium 1xxx address to my segwit 3xxx or bc1xxx address that I generated from a paper wallet?
Can I send out from my mycellium 1xxx address to my segwit 3xxx or bc1xxx address that I generated from a paper wallet?


The 3xxx addresses are P2SH addresses, and they have been around since 2012. They're usually for multisig policies, and only recently can also be used for segwit outputs. However, as the sender doesn't know or care what kind of script the hash is for, any wallet that can send to P2SH will support sending to such segwit address. This is the reason why segwit can be encapsulated in P2SH in the first place: to be compatible with old wallets.

bc1xxx addresses are new, specific to segwit, and likely only available in software designed to be compatible with segwit.

The best way to know what software supports what style addresses is to try, of course.