This issue is only related to American version of Samsung phones with Android 6. If you have International or any other version see issue
#507 for solution to call recording issues.
It seems that changing recording audio source to VOICE_COMMUNICATION or AUTO as per issue
#507 is not working on American variants of Samsung phones.
I've had few users with American version of Samsung phones including S6/S6 Edge/S7/S7 Edge, Note 5 and Note 4 trying settings on issue
#507 without any luck. I've asked all of them to try different call recording apps and all had same result.
Therefor, I believe call recording is no longer supported on American variant of Samsung phones with Android 6.
This is similar to what happened with S4. International version of S4 supported call recording perfectly fine while American version did not.
I believe this is not intentional but rather a bug escaped to the production release of Android 6 for American versions of Samsung phones. This could be mainly due to customization required by American carriers.
Please post your experience to this page so we can investigate further.
Please do not forget to add
Your phone name/model
Build version from Phone Settings> About> Software version