I'm not a lawyer and I'm not from Nintendo, so take that into account first.
The safest thing to do is to not use the sprites from an already copyrighted IP. Nintendo owns the Mario sprites and as such you can get in trouble if you use them without their express permission. You can use the same gameplay but not the sprites. If it is for anything that someone other than your household would see, I would say rule-of-thumb is don't do it.
Always remember that just because there are games out there using the sprites does not mean that it is okay with Nintendo, they either may not know about it or have other priorities. As long as Nintendo is doing something to protect and reinforce their copyright and trademark it stays theirs.
tl;dr Don't do it, Nintendo's inaction against others does not mean they give permission.