Arcade and 16bit consoles are quite different, but N64 isn't as involved as you'd think.
MK Trilogy and MK4 were made by different companies and likewise their compression is different. Trilogy uses gzip, MK4 uses EDL. Moves watchdog a set of controller input buffers, then compare to lists of individual character moves. The buffers are easy enough to find; backtrace copiers from the SI rdram target address, then see which routine is receiving requests to read them. Midway was sloppier with threads than Eurocom, so you'll probably find Midway a little easier. There should only be 2-3 active uses during gameplay, so it should be easy enough to locate the entire moveset engine.
Movesets are stored using standard button codes, and control schemes will just remap these a default. Eurocom always goes overboard with tables, so expect pointers to tables of pointers, each pointing to a button sequence and an animation/action/function/etc. Anyway, the button sequences will be separate from the code they trigger, and tables are used instead of hardcoding. Only trick there is cleaning up room and shifting data so you can put your new, usually longer, sequences in. Unfortunately, unless you're really lucky, they probably stored everything as short values. Otherwise, you could double available space by changing the reader to pull unsigned HWs instead of words.
Both are recycled engines, so they were originally designed with the intention of altering this kind of data. Mostly pointer redirection and shuffling.
Get familiar with a hex editor and debugger. It's not super difficult, but rather time consuming.