No es necesario que formatees nada, la partición linux por lo que he entendido no ha desaparecido, simplemente al eliminar windows y reinstalarlo te ha escrito el sector de arranque del disco duro (MBR) y evidentemente se ha cargado el Linux Loader (LILO), lo único que tienes que hacer es reinstalarlo, y para ello puedes arrancar el ordenador desde el cd de la mandrake y en el boot, escribir rescue, con lo cual entrarás en las opciones de recuperación de linux, siendo una de ellas precisamente el recuperar el lilo.
Un saludo