How to Connect Dc motor with encoder (pololou) with motor shield and Arduino Mega 2560?
A quick look on Pololu's website reveals that:

    Color   Function
  --------  --------------------------------------------
    Red     motor power (connects to one motor terminal)
    Black   motor power (connects to the other motor terminal)
    Green   encoder GND
    Blue    encoder Vcc (3.5 – 20 V)
    Yellow  encoder A output
    White   encoder B output


Thus: Red goes to M1A and Black goes to M1B on the motor shield.
The remaining wires are for the encoder and go to Arduino pins.
Green goes to Arduino GND, Blue goes to 5V, Yellow and White go to the
digital i/O pins of your choice.

Note: Your motor shield has extra 5V and GND pins so you can connect the Blue and Green wires there.