Am I correct in also assuming it's 8 frames? Looks that way to me with the smoothness. I have two ideas on why it seems like he's stomping:
1. Just due to the character's looks - The outfit gives a certain knightly demeanor, which might give credence on why we're seeing stomping.
2. Not quite sure, but it feels like it's bobbing too much? When the leading foot hits the ground, the sprite might be lowered one pixel too much and causing a stomping effect. It feels bouncy, which gives it a feeling of marching.