Make sure you're using -video opengl and not -video soft.
If you are using opengl and it's still slow, try setting -antialias to 0. I don't know if this is still the case in any Mesa drivers today, but line antialiasing (not the same thing as fullscreen antialiasing, which is what PC games use) used to hit software fallbacks on some cards. In MESS/MAME, -antialias only affects systems with vector monitors (Vectrex, some early 80s MAME games) and the boxes around UI windows. Turning it off won't affect image quality for anything else.