I think Marie is much prettier than Mary. And how about a shorter form of Elizabeth like Eliza? Marie Eliza or Eliza Marie is really cute!
Elizabeth Marie nn Lizzie
Personally, I'd put Elizabeth in the first name spot because it has so many great nn's while Mary has none.
Madeline (Maddy) is close to Mary!
Then some name/nickname ideas:
Mary: Margo, Margot, Maisie, Millie, Molly, Marion, Miriam, Mimi, Millicent (not something I would pick, but an option none the less), Mackenzie.
Elizabeth: Eliza, Lisa, Beth, Bethany, Elisabetta, Elodie, Ellie, Eleanor, Betsy, Betty.
Or how about making her middle name as something double barreled? Like Mary-Beth (ie. Olivia Mary-Beth)
If you do go with Mary Elizabeth, I would try to give her a very unique other name too. Mary and Elizabeth are both very common girls names, so why not go for something more unique as a second middle or first name?