It's not so much the number of frames as much as it's simply that Samus's default running animation doesn't seem like the artists took the number of frames into account when designing the animation.
For example, Samus seems to move slower than the animation would suggest, so what about if you made her leg movement less pronounced. You said that the main character in this isn't going to be Samus, so having a character that moves in a more subdued, "Oh shit, I'm going to die any moment!" manner rather than Samus's badass demeanor would make sense, and would possibly work better in the limited frames for the animation.
While I concede that it's probably a lot of work to get an additional movement frame in the animation, would it be difficult to slow down the animation a bit? What if you were to take the leg positions from something like Castlevania, and use something like that? You'd have more natural-looking movement while keeping the number of frames you currently have to work with.