That quote is referring to a game that runs at a 640x480 resolution. According to a quick search, most N64 games including Mario 64 run at 320x240 which reduces the fill rate requirements by a factor of 4. That would leave plenty of room for using the Z-buffer along with texture sampling.