You're asking me a legal question on the jurisdiction of the federal government, and I think the Supreme Court of Canada decided that in a case called Mangat. The B.C. law society argued that the federal government had no jurisdiction to regulate consultants, and the Supreme Court of Canada concluded that it did. So the question of which body--federal or provincial--has the jurisdiction has been decided by the court.
There is a second related question, and that's in terms of competence. I would agree that one possible solution would be for the regulation to fall to the provincial law societies. In Ontario, for example, the provincial law society now regulates paralegals. Since the law society has expertise over the regulation and all the experience in regulating in consumer protection, it would make sense to have them be the regulatory body. Albeit many people think the law society doesn't do it that well, it does have more experience than anybody else in the area, and it does its best. So now that the law society is into the area of regulating paralegals in Ontario, it would make sense for them to be the regulatory body.
Now, that would work if every law society in every province were prepared to undertake the responsibility of regulating the paralegals in the province. But it would be the preferred solution, for sure.