Yeah trace functions are big eating things

why not use simple 2D box collision algorithm , caus the game works in a 2D plan
for jumping on ennemies , you could detect when the box collision of mario is over the middle of the second box collision(ennemie)

but for level collisions i don't know how else you could do ?
perhaps cutting your level in more parts and making all distant ones
passables could speed the game ?

you said the game runned at 60 frame/s , so why not increase mario speed
caus in the video he looked really slow.

Keep it up