Supongo que el boton que tenes para eliminar el registro es un input del tipo submit y al hacerle click procesas el form.
Entonces, cambiale el tipo a button y en el evento onclick armate una funcioncita en javascript que tire la confirmacion.
<input type="button" onclick="javascript
:eliminar();">
la funcion eliminar podria ser mas o menos asi
Código:
function eliminar()
{
if(window.confirm('Desea eliminar el registro???'))
{
document.nombreDelFormulario.submit();
}
}
A grosso modo seria algo asi.
Saludos.