Regresando al primero:
 
en eliminacion.php yo creo que el codigo debe ser así:   
Código PHP:
Ver original<?php
require('conexion.php');
//variable GET
$idemp=$_GET['id_subcategoria'];
$idcat=$_GET['id_categoria'];
$elimina="DELETE FROM mn_subcategorias WHERE id_subcategoria=$idemp";
 
//include('categorias.php');  ELIMINALO, con esto está imprimiendo todo el menu
 
//ACA DEBES IMPRIMIR SOLO LAS SUBCATEGORIAS, LAS ACTUALIZADAS
$resultado = mysql_query("select * from mn_subcategorias where id_categoria = $idcat order by subcategorias", $conexion);             echo "<div class=subcategorias>";
            echo "<a href=#>".$fila['subcategorias']."</a>";
             echo "<a style=cursor:pointer; onclick=eliminarDato(".$idcat.",".$fila['id_subcategoria'].")><img src=eliminar.gif align=right height=13px width=13px></a>";
            echo "</div>";
        }
        
?>
  
categorias.php    
Código PHP:
Ver original<div id="categorias" >
    <div id="firstpane" class="menu_list">
<?php
    $itemscategorias = mysql_query("select * from mn_categorias", $conexion);     echo "<p  class=menu_head> " . $fila['categorias'] . "</p>";
    echo "<div class=menu_body id=".$fila['id_categoria'].">";
    $resultado = mysql_query("select * from mn_subcategorias where id_categoria = $fila[id_categoria] order by subcategorias", $conexion);             echo "<div class=subcategorias>";
            echo "<a href=#>".$fila['subcategorias']."</a>";
            echo "<a style=cursor:pointer; onclick=eliminarDato(".$fila['id_categoria'].",".$fila['id_subcategoria'].")><img src=eliminar.gif align=right height=13px width=13px></a>";
            echo "</div>";
        }
        echo "</div>";
    }
?> 
    </div>
</div>
  
y este es el JS, funciona con JQuery:    
Código Javascript
:
Ver originalfunction eliminarDato(idcategoria,idsubcategoria){
                ajax(idcategoria,idsubcategoria)
        }
        function ajax(idcategoria,idsubcategoria){
            $.ajax({
              url: "eliminacion.php?id_subcategoria="+idsubcategoria+"&id_categoria="+idcategoria,
              contentType:"application/x-www-form-urlencoded; charset=utf-8",
              type:"GET",
              error: function(){
               alert('Error');
              },
              success: function(data){
                  $("#"+idcategoria).html(data);
               }
            });
        }
  
A ver que como te sale.