If you wouldn't mind changing the number you give to people, you can record phone calls with Google Voice. Sign up for an account, link your mobile phone to it, and provide the other person with your Google Voice number, and then press 4 during a call to start recording.
I'm not aware of any actual app that can do it that's available on WP8.1 DP right now.