Before Marshmallow (2015), recording phone calls was behind the same permission as recording the mic. This was obviously bad as voice calls are much more privacy sensitive than the mic. In Marshmallow, phone calls recording was updated to be guarded by a new permission, a system one, so only system application can access it.
Nevertheless, there were multiple ways to bypass the new system permission, which call recording apps made use to continue recording calls even without the system permission. Those ways were fixed one after the other as part of securing and refactors of the audio stack. The last such bug was fixed in Android 9.
Any OEM can bundle a call recording apps, it's just that many don't.