My understanding is that if I implement an ERC20 token but also add an ability to burn some tokens, that token is no longer considered ERC20 token, because when coins get burned, the total amount decreases. The question is - are there ANY negative effects? Incompatibility with any wallets?
The assumptions you make are untrue.
Any token that correctly implements EIP-20
transfer() etc. functions and events is EIP-20 compatible. What other functions or traits the token has does not make it incompatible.