Give child-categories same class (the parent category-slug) as parent in menu list?

If you want only 2 levels, you may use the parent parameter. Example

<?php
$args = array(
    'hide_empty' => 0,
    'parent' => 0
);
$categories = get_categories($args); 
$menu = '<ul class="nav">';
// iterate through your categories
foreach($categories as $category) { 
    $menu .= '<li class="' . 'cat-item category-' . $category->slug . '">' . '<a href="'.get_category_link($category->term_id ).'" title="' . esc_attr( sprintf( __( "View all posts in %s" ), $category->name ) ) . '">' . $category->cat_name . '</a>';
    $children = get_categories( array('parent' => $category->term_id) );
    if($children && !empty($children)) {
        $menu .= '<ul class="subnav">';
        foreach ($children as $child) {
            $menu .= '<li class="' . 'cat-item category-' . $category->slug . '">' . '<a href="'.get_category_link($child->term_id ).'" title="' . esc_attr( sprintf( __( "View all posts in %s" ), $child->name ) ) . '">' . $child->cat_name . '</a></li>';
        }
        $menu .= '</ul>';
    }
    echo '</li>';
}  
$menu .= '<li class="menu-border">' . '</li>' . '</ul>';
echo $menu;  
?>

If you have unknown number of levels, you can implement a similar logic as a recursive function