Ti conviene lascaire le funzioni cosi` come sono, e chiamarle a seconda di un paramentro.
Tieni presente che le tue funzioni usano strumenti deprecati e poco efficienti (eval). Le riscrivo senza.

codice:
<script language="JavaScript">
var selezionate = false;

function Sel_All() {
  The_Form = document.elimina;
  for (var i=0; i<The_Form.length; i++){
    if (The_Form.elements[i].type == "checkbox"){
      The_Form.elements[i].checked = true;
    }
  }
  selezionate = true;
}

function DE_Sel_All() {
  The_Form = document.elimina;
  for (var i=0; i<The_Form.length; i++){
    if (The_Form.elements[i].type == "checkbox"){
      The_Form.elements[i].checked = false;
    }
  }
  selezionate = false;
}
</script>

Il bottone dovra` essere:
<input type="button" onClick="if(selezionate) Sel_All(); else DE_Sel_All();">

Ciao
Michele