Design and development of alternative logos and branding materials, including complete mock up of products, stores/restaurants, ads, etc. Focus groups, surveys, polling. Psychological studies, etc. When you're a multi-billion dollar brand with established worldwide recognition, you dot every I twice and cross every T three times when assessing any significant changes to your branding and image. Does it need to cost millions? Certainly not, but they're given a big budget and they're going to use all of it in case things don't go smoothly - those in charge of developing a new look want to be able to say they turned over every possible rock, explored every possible idea, etc.