Você não especificou um sistema operacional. Esta resposta assume o Windows.
Meu primeiro pensamento foi um comando simples como
for %f in (*.png) do rename "%f" "New_%f"
Mas um arquivo chamado a.png
foi primeiro renomeado para New_a.png
e movido para baixo na ordem alfabética :-( O loop renomeou este arquivo com um tempo segundo para New_New_a.png.
Portanto, isso deve ser feito em duas etapas:
dir /b *.png > png.txt
for /F %l in (png.txt) do rename "%l" "New_%l"
del png.txt
A primeira linha cria um arquivo de texto contendo os nomes de todos os arquivos png no diretório atual. A segunda linha analisa cada linha do arquivo e renomeia o png.