It might be legal from Canada's perspective, but that doesn't necessarily mean legal action couldn't be taken in the US. Is there something specific to the law on recording phone calls that makes this not a problem?
You can sue anyone for anything anywhere, but I cannot imagine the Canadian police being interested in a citizen doing something lawful in Canada if the California (or wherever) cops call to complain be broke a Californian law.
And I can even less imagine a civil action demanding damages or court actions in Canada for doing something legal there. It would be like a Saudi company suing a US driving school that teaches women.
I don't think there's a there there as far as liability or worry. IANAL, of course.