Falcon has a tough time against all short characters; I'm not sure why you think Mario is so special. Kirby, MK, Pikachu, and Ivysaur are all shorter and tougher. Ivysaur is so short that in his stand animation you can't up-B him from the ground next to him (an odd find while collecting kill percents).
Anyways.... NAir to Jab still works, and for Mario he doesn't have much range, so you can usually just hit him with UTilt/FSmash if he approaches in the air (except with fireballs) and DTilt outranges most of his ground stuff. His DSmash is a good move to SH-Falcon Punch since it's really low to the ground, but you'll have to anticipate the DSmash and be in front of him so that it hits him when he's doing the backwards part of the move (you come down after the forward kick). In the air his NAir, UAir, and BAir are all pretty fast, so try to avoid him or UAir/Falcon Dive him if you are below or even with him and in the air. DSmash and FSmash are your best kill moves for Mario because they have pretty good range.