In 2011 , Elvis Costello appeared as himself on Sesame Street to perform a song with Elmo and Cookie Monster , titled `` Monster Went and Ate My Red 2 '' , a play on ( The Angels Wan na Wear My ) Red Shoes .
In 2011 , Elvis Costello appeared as himself on Sesame Street . He did a song with Elmo and Cookie Monster , titled `` Monster Went and Ate My Red 2 '' , a play on ( The Angels Wan na Wear My ) Red Shoes .