Whether I have to scan all types of addresses to discover BIP44 wallet from mnemonic? Let's assume that I am going to create a new address in bitcoin HD wallet knowing only mnemonic words and that previously addresses were generated according to BIP44.
BIP44 gives an algorithm how to perform discovery but one thing is not clear for me: whether I should check all possible address types described in the wiki (P2PKH, P2SH, Bech32) in outputs of transactions or there is some simpler way to check that particular index of child node was used to receive payments?
Any help will be apprecated, thank you!
That depends on what kind of wallet you have.

The derivation path is designed to tell you which types of addresses you need to. 


m/44 means just regular addresses
m/49 means segwit nested in P2SH.
m/84 means native segwit.


Wallets such as electrum allow you to select which address type to check, and then perform the account recovery process you linked in your post. Ledger and Trezor similarly expect you to select address type when opening the companion apps on the computer.

If you are building a wallet or tool, you should either prompt the user to select the address type, or iterate all three combinations (and give an option to enter a manual derivation path for non-compliant wallets).