It is perfectly legal to record an ordinary telephone call “provided one of the parties” knows of the recording. It has been used by reporters who are too lazy to take shorthand or notes for ages.
Google however says call recording is no longer allowed via the accessibility APIs. Since the accessibility APIs are the only way for third-party apps to record calls on Android, call-recording apps are dead on Google Play.
The Google Play support page says: "The Accessibility API is not designed and cannot be requested for remote call audio recording."
Google's ban starts on May 11, the first day of Google I/O and there is no clear reason why it has become necessary.
The Google Recorder app is a product built entirely around the usefulness of recording conversations. Google doesn't seem to have a problem with call recording when it comes to its own apps, either -- the Google Phone app on Pixel phones supports call recording in some countries.
Google just doesn't provide the proper APIs to let third-party app developers compete with it in this market, and now it's shutting down their attempted workarounds.