I was in a similar situation. I was flying from Melbourne, Australia to Kuala Lumpur by Malaysian Airlines and then KL to Singapore by Singapore Airlines. When I checked in at Melbourne, I was told that I will be able to collect my bags at Singapore directly. Well, this had never happened with me before, so I was a bit hesitant.
At KL airport, my restless mind couldn't control it and I went to the baggage claim area. Obviously, I didn't find my bags there, so I spoke with this officer there and explained the situation to him. He assured me that I will get my bags at Singapore. Lucky for me, he wrote it down on a paper and signed it.
At Singapore, I didn't get my bags. Officials said that it wasn't their responsibility. They can't do anything about it. They asked me to speak with Malaysian Airlines. Malaysian Airlines said that they hold no responsibility as the bags were transferred to Singapore Airlines. So, after all this back and forth, I pulled out the letter and suddenly Singapore Airlines did a U-turn. They checked with Malaysian and confirmed that my bags will be delivered the next day.
So, all I can say is HARASS them. Contact Air France and get confirmation. Contact Air Canada and ask them for updates. This is a pretty sad situation, I know. But, you should get your bags in a day or two. Sometimes, airlines send the bags directly to the final destination. So, I'd say contact Air France first and see on which flight was it sent.
Good luck.