Bunyan doesn't sound like a French name to me. Also, didn't it start as a Midwestern U.S. folktale? Like Wisconsin and Minnesota? That's what I thought.
I've heard that he was the continuation of Joseph "Jos" Montferrand, a French Canadian logger and legend born in Montreal, who worked in the Gatineau and Outaouais region, known also as big John Mufferaw. He then moved south of the border to continue working as a logger where he became known as Paul Bunyan.
Bunyan sounds the same as some old French Canadian swear word, but is written differently. I think the real spelling would be something like "bon yenne", and also resembles a French Canadian folklore named "Bon Jean".