First make a white-on-black mask of your logo/text and blur it.
Then create a repeating (tileable) solid noise texture (GIMP used here)
Use the Map->Tile… filter to create a 3×3 tiled pattern (in this example, 128×128 x 3 = 384×384) for the next step to ensure our texture is still repeatable – we’ll keep only the center part.
Use Blur->Motion Blur… to blur the texture upward and keep only the center 1/3rd (back to 128×128)
Multiply both textures together on the GPU and use this for opacity.
Then animate it by moving the pattern texture upward over the mask texture:
Done for the animation part.
Then you can apply a gradient map (black -> red -> yellow -> white) to give it fire colours:
Other colours can be used create a ghastly blue fire, a light yellow aura field, a more smoky effect, etc.
Now if you combine this as additive over your logo and the 3D render you get the wanted effect:
+ + =
The effect can darkened by adjusting the mask and/or pattern brightness, and/or vertex color, and/or gradient color map to the designed level.
You can even use two textured patterns together (Mask * Fire Pattern * Fire Pattern) at different speeds and directions to create a more complex fire effect.
Technically on the N64 they may have created an approximation of the mask using a triangle mesh and vertex color instead of the mask texture due to the N64’s hardware limitation regarding textures but the end result is the same ((vertex color * pattern texture) vs (mask texture * pattern texture)).
We can still use vertex colour but 20 years later we can make our lives easier and just use 2 textures or more, even today’s mobile GPUs can handle an extra 256×128 gray texture without problem.
There are a few ways you could do it but off the top of my head,
1) Have the flames + logo all in one image and essentially sprite sheet animate it.
2) Render the logo in a UI layer and place some UI layer particle effects around it.
From the looks of that image, it looks like there are 3ish layers shield&sword, flames, text (ordered from back to front).
There will be many ways to get a similar effect, which you chose will be down to what engine you are developing in and what you are able to implement.
If the ROMs include a small flame texture, then I would guess this is being done with some kind of particle effect.
This would be done by first putting a sprite on the screen for the title and logo. Then place a number of particle emitters that create a flame effect behind the title sprite. That is, their Z/screen depth is such that they render behind the title.
Here’s an example of using GameMaker particle effects to create flames that might give you some thoughts on the potential of this approach…