I understand that you are receiving the error "Multifactor authentication save failure : Unable to save the Azure AD multifactor authentication policy."
To add to Dillon Silzer's comment, I would recommend adding all of the policy users to a group and also adding the exclusion users to a group, and then adding those groups to the policy. Since you have a large number of users, you might be hitting some limitations.
I tested in my own tenant with both users and groups and was able to save the policy:
Other things to confirm:
- Check that you have a valid Premium P2 license assigned to use Identity Protection features. If your license expired, you might run into access issues.
- Check that "Users can use the combined security information registration experience" is selected.
I've also reached out to the Identity Protection team to confirm if anything could have changed since I was unable to reproduce your issue.
If the suggestions do not work, feel free to send me an email so that we can troubleshoot further - AzCommunity@microsoft.com ("Attn: Marilee Turscak").
If the information helped you, please Accept the answer. This will help us as well as others in the community who may be researching similar information.