Why is built-in call recording such a rare feature on Android devices?
I think it mostly has to do with both of the following:


A lack of demand for the feature. While a small minority of users may want this feature, most "normal" users probably never even think about it.
The laws in the US regarding recording phone calls are relatively complex. They usually vary from state to state (source). Companies probably do not want to expose themselves to additional liability. 


If #1 was to change so that a sizable number of people want this feature, then a company would be more likely to put the effort in to make sure that the feature works legally.