In tpl_mega_menu.php, find
<li class="submenu categories-li" <?php if (MENU_CATEGORIES == 'false') echo "style=\"display:none; \""; ?> ><a href="<?php echo zen_href_link(FILENAME_DEFAULT); ?>"><?php echo HEADER_TITLE_CATEGORIES; ?></a><!-- bof cateories -->
<div class="dropdown_1column">
<div class="col_1 firstcolumn">
<div class="levels">
<?php
// load the UL-generator class and produce the menu list dynamically from there
require_once (DIR_WS_CLASSES . 'categories_ul_generator.php');
$zen_CategoriesUL = new zen_categories_ul_generator;
$menulist = $zen_CategoriesUL->buildTree(true);
$menulist = str_replace('"level4"','"level5"',$menulist);
$menulist = str_replace('"level3"','"level4"',$menulist);
$menulist = str_replace('"level2"','"level3"',$menulist);
$menulist = str_replace('"level1"','"level2"',$menulist);
$menulist = str_replace('<li class="submenu">','<li class="submenu">',$menulist);
$menulist = str_replace("</li>\n</ul>\n</li>\n</ul>\n","</li>\n</ul>\n",$menulist);
echo $menulist;
?>
</div>
</div>
</div>
</li><!-- eof categories -->
and replace the <div class "levels">...</div> with <ul class="levels">....</ul> from the "quicklinks-li" above it, ie the first item in the mega menu. Then replace each <li> link - the a href="...." content with your links to your categories, and <?php echo whatever; ?> with your category name. Where your category name replaces 'whatever'. So you will end up with a list of your categories replacing the current dropdown list. Back up your tpl_mega_menu.php before you try it.
I hope that makes sense.