I'm the guy Gary M. wrote about, I was 76' overall length and 114" wide towing a boat up last spring. I contacted Canada DOT (googled) and got two permits for $15. BC only allows 65' and I think Yukon allows 75' but not sure what it is for motorhome towing. Anyway I only had to buy two permits, two days ahead of time. Had to also give them the route we were taking. I got a different story everytime I called, so it the agent you get can't help wait five minutes and call back. They emailed me the permit and I printed it out and signed. I had it ready when I drove up to the border.
At the border crossing they didn't even want to see the permits. I'm sure most of the people towing trailers with 40 and 45' motorhomes do not permit. Those lengths are also in legal in quite a few of the lower 48.