Начиная с версии 1.5 существует класс java.util.concurrent.TimeUnit, используйте его следующим образом:
String.format("%d min, %d sec",
TimeUnit.MILLISECONDS.toMinutes(millis),
TimeUnit.MILLISECONDS.toSeconds(millis) -
TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(millis))
);
Для версий ниже 1.5 Вы должны использовать
int seconds = (int) (milliseconds / 1000) % 60 ;
int minutes = (int) ((milliseconds / (1000*60)) % 60);
int hours = (int) ((milliseconds / (1000*60*60)) % 24);