Lo adecuado es mantener la mayúscula inicial en ambos elementos y, como conservan cierta independecia debida al guión, también conservan sus respectivas tildes: Vélez-Málaga.