We were able to fix this issue with the following steps:
Add domain/subdomain and return URL to your Apple account
Check the length of the domain in redirect_uri it shouldn't be too long
In our case, domain length was 54 symbols and it start working when we reduce it to 49 symbols. It looks like there is a limit to the domain name length of around 50 symbols.
It was easy to reach this limit since we use a Cognito domain with a prefix and prefix attached to quite long domain name ".auth.eu-central-1.amazoncognito.com".