O togli l'onClick dal link e al lo metti sul bottone eliminando l'ancora, oppure lasci l'ancora e togli il bottone ma invece di mettere il confirm in onClick lo metti nell'href

Così:

<head>
<script language="javascript">
function Conferma(id)
{
if(confirm('Sei sicuro di voler cancellare definitivamente questo record?'))
{
document.location = 'pagina.php?action=elimina&id_record='+id;
}
}
</script>
</head>
<body>
<?="<a href=\"javascript: Conferma('".$row['id_record']."')\">elimina</a>"?>
</body>