With the pelvis rocking about like this, the whole character is going to jerk and shake while running. The body should be more or less stable for the resulting animation to look right.
And I'd try and animate the whole character, not just his legs. Maybe even in some sort of a specialized animation programme, like Flipbook or Abobe Flash, just to make things easier for yourself. You can always scale the result down and make it into a pixel animation later.