Должно помочь следующее:
У контейнера Яндекс-карт установлен z-index равный 1. Просто установите значение больше (например, z-index: 500) и укажите абсолютную позицию (position: absolute) вашей легенды. Ну а потом устанавливайте позицию легенды при помощи свойств left и top.