Cents follow:
First you can't make the game without the game engine but how would you know how the game engine should work if you don't know what sized sprites your going to use and how many of them without drawing the graphics first? How do you stay attentive drawing the graphics?
You can usually have two kind of game engines: those that are limited to what the hardware allows, and those that try to hide hardware limitations to the programmer. The number of frames, etc. should not be a limitation, though. At worst, you'll have (on gaming hardware) restrictions such as "16x16, 32x16, 16x32, 32x32, 64x32, 32x64 or 64x64 only", and have may end up with a 24x24 sprite on a 32x32 frame with 70% of the pixels being fully transparent.
(I'm thinking of making this game for either a Sega Genesis or a Super Nintendo)
I'd say forget it, esp. for the SNES, because it has really ugly programming (assembler only) and unless you're a veteran programmer, you'll completely get overwhelmed by technical details even with something "as simple" as the game engine of (say) Cave Story ... The Nintendo DS (and the PSP to some extent), on the other hand, show similar hardware than those beloved 16-bit consoles, but with 32-bit CPUs that can be dealt with like a PC, with "higher" level language (C, C++). Not that it will make your work as easy as in a flash game, but well, playing a game on a gaming system is definitely more fun than with a keyboard 
How do you come up with a system of designing the game that allows you to do EVERYTHING?!
You don't. Not that way, at least. You can come up with an engine that handles 90% of your ideas, and you write custom code for the remaining 10%. Then you ensure you can "register" custom code to the game engine and make it trigger your custom code e.g. when the player enters a given area.
I have a lot of crazy game ideas that don't involve just having enemy sprites walking on a non-moving background layer. For example, having a wall in the background crack and then the ceiling collapse on you, you can't achive with just the "sprites on one playfield background" kind of engine. It wouldn't work because it will require the top of the background to be turned into two backgrounds and the second will be also as much as part of the game as the first background.
In a game engine, i'd be handling a situation like that by first editing the map (e.g. so that a previously solid area now is no longer solid) and generating sprites/polygons for the cracking wall.
What about compressing graphics?: If you do all the decompressing before you start the level you might run into RAM limitations; if you do real-time compression you might have som miserable slowdowns (unfortuanately, a lot of Snes games relied on this method, I heard from someone); and if you don't use compression you might run into ROM problems.
Guys handled that with extra hardware ... cartridge shipping RAM plus ROM and a decompressing "DMA" chip that moves and unpacks at once while the (slow) CPU of the console does the rest. Honnestly, if you instead opt for the DS, you'll have 4MB of RAM, +640KB of video ram and plenty of CPU time to unpack the next sequence... Alternative is to have some kind of "intermission" sequence where CPU needs are limited (e.g. a 'boost up' in a shoot'm'up where there are no ennemies to avoid) so that you can focus on unpacking the rest of the level. That's something you'll work on *wayy* after, anyway. This is typically a "technical detail" that you can handle later, just having two playable zones during your demo times.
** edit after a couple of PM exchanged with Beoran **
C/C++ is afaik "state of the art" (maybe the "Golden Way" too) to squeeze the best of your modern handheld gaming console (GBA, DS, PSP), but that golden way is made of spiky tiles that may throw you deep into the pitfall of segmentation fault that only meditation of the guru can avoid. Put otherwise, it's certainly not the easiest thing to start with if you have no previous experience on game programming.
I read some interviews with real programmers who worked on old 16-bit games. Believe it or not, most Super Nintendo were NOT written in assembly, instead they were written in a scripting language.
When using raw assembly, the 65816 running at 3.58 mhz is actually almost as fast as a 68000 running at 7.67 mhz, but because of the scripting languages used, this is not the case. Motorola 68000 has very orthogonal and more powerful instruction set, but is held back from having every instruction using a very large number of cycles. The 65816's instruction set is generally weaker, but every instruction takes by far less cycles to perform than the 68000 does. Thanks to the fast instructions, the 65816 is near twice as fast as a 68000 running the same speed, WHEN they are both fully optimized; but when they are not fully optimized, the 65816 falls back in speed more than the 68000 does. This is because of the 65816's weaker instruction set.
With the 68000, you often get the code right (fully or near fully optimized) the first time. When you do 65816 assembly, chances are, the code will be far from perfect on the first try, and it would need a very large amount of hand optimizing to reach it's full potential. When the 65816 code is fully optimized there is a huge huge difference in speed compared to unoptimized 65816 code. Much, much larger than the difference between unoptimized and optimized 68000 code.
This gets way, way exaggerated once you use higher-level/scripting language and have the computer do all the translating into assembly for you. Big complicated things like games were programmed with script-engines to speed-up development. Add to that, Nintendo went all cheapskate, and limited the amount of 3.58 Mhz game ROMs and made far too many games in 2.68 Mhz, just to make a little extra profit on game carts.
Add all of this up, and the Super Nintendo's CPU only ran about a hundredth of what it was actually capable of doing. The only exceptions to this was, Space Megaforce, Smash TV, Wild Gun, and maybe very few others.
