Использование встроенных возможностей MapView и Overlays для рисования анимации, скорее всего, убьет вашу производительность. Мое предложение:
1) Объединить MapView с другим View. MapView предоставит вам необходимые координаты экрана, а другой вид будет служить основой для анимации. Оба вида должны занимать одинаковые позиции на экране (используйте структуру кадра);
2) Как только вы получите позиции маркера карты, который хотите анимировать - удалите его с карты и начните выполнять анимацию движений маркера, используя второй вид. Здесь вы можете использовать специализированные классы анимации для Android (т.е. Animation, AnimationUtil, AnimationSet)
3) Как только вы покончили с анимацией - добавьте маркер в наложение карты, теперь в его новой позиции и лишите законной силы наложение
Возможно, может быть более оптимальный подход (т. Е. Использовать анимацию непосредственно на холсте MapView), но суть в том, что вы должны использовать специальный механизм анимации для предотвращения проблем с производительностью.