Do you have the marriage certificate? Normally I'd expect to find him listing parents.
http://www.afhs.ab.ca/data/census/1906/manitoba/10/mb_10_05a...- here he is in 1906, says he emigrated same year.
Canadian immigration records are not indexed for that year, though.