Deleting all categories on magento via the admin panel can be time consuming. A quick way to do this would be thru phpmyadmin.
Before running this code please make sure you have a backup of the entire database.
SET FOREIGN_KEY_CHECKS = 0; TRUNCATE TABLE `catalog_category_entity`; TRUNCATE TABLE `catalog_category_entity_datetime`; TRUNCATE TABLE `catalog_category_entity_decimal`; TRUNCATE TABLE `catalog_category_entity_int`; TRUNCATE TABLE `catalog_category_entity_text`; TRUNCATE TABLE `catalog_category_entity_varchar`; TRUNCATE TABLE `catalog_category_product`; TRUNCATE TABLE `catalog_category_product_index`; INSERT INTO `catalog_category_entity` (`entity_id`,`entity_type_id`,`attribute_set_id`,`parent_id`,`created_at`,`updated_at`,`path`,`POSITION`,`level`,`children_count`) VALUES (1,3,0,0,'0000-00-00 00:00:00','2009-02-20 00:25:34','1',1,0,1), (2,3,3,0,'2009-02-20 00:25:34','2009-02-20 00:25:34','1/2',1,1,0); INSERT INTO `catalog_category_entity_int` (`value_id`,`entity_type_id`,`attribute_id`,`store_id`,`entity_id`,`value`) VALUES (1,3,32,0,2,1), (2,3,32,1,2,1); INSERT INTO `catalog_category_entity_varchar` (`value_id`,`entity_type_id`,`attribute_id`,`store_id`,`entity_id`,`value`) VALUES (1,3,31,0,1,'Root Catalog'), (2,3,33,0,1,'root-catalog'), (3,3,31,0,2,'Default Category'), (4,3,39,0,2,'PRODUCTS'), (5,3,33,0,2,'default-category'); SET FOREIGN_KEY_CHECKS = 1;