Hmm..it's kinda hard for me to describe how I beat the Mario players I've confronted. I can give you acouple tips, if they are far away, and try to shoot fireballs at you, just whack at them with your sword, and they'll disappear, also, Link's standing neutral A acts as a barrier, meaning it'll stop pratically all of Mario's attacks, since your range is farther. His slide can't work, because if it hits the sword, either they get hit, or Link and Mario just deflect oneanother.
Also, say if you swipe, and they cape you, you can either roll away, or turn back around with your forward tilt attack, this'll catch them off guard. Usually when I do this standing still neutral A swipes, I'll see that Mario will try to roll behind me but during this time, if you can pick it up, just SpinAttack. I rarely throw my projectiles at Mario because he capes, so I'll usually just turtle and have him come to me, allowing me the advantage.
My tatic for defeating Mario is using Link's range, beware however, Mario's forward Smash has surprisingly far range. The plumber will have more of a problem going against Link than Link going against him. Don't worry, try my tatic, hopefully it'll help, remember, turtle, but know when to get away.
Basically I just play marathon match with Mario.