<?php
wp_nav_menu(array(
    'theme_location' => 'songs-category',
    'container' => false,
    'menu_id' => 'nav',
    'menu_class' => '',
    'items_wrap' => '<ul id="nav"><li class="active"><a href="#" data-slug="4,5,6,7,8,9" class="xyz">All</a></li>%3$s</ul>'
    ));

<ul id="nav">
    <li class="active"><a href="http://domain.com/" title="All">All</a></li>
    <li><a href="http://domain.com/category/category1/">category1</a></li>
    <li><a href="http://domain.com/category/category2/">category2</a></li>
    <li><a href="http://domain.com/category/category3/">category3</a></li>
    <li><a href="http://domain.com/category/category4/">category4</a></li>
    <li><a href="http://domain.com/category/category5/">category5</a></li>
    <li><a href="http://domain.com/category/category6/">category6</a></li>
    <li><a href="http://domain.com/category/category7/">category7</a></li>
    <li><a href="http://domain.com/category/category8/">category8</a></li>
    <li><a href="http://domain.com/category/category9/">category9</a></li>
</ul>

<ul id="nav">
  <li><a href="#" data-slug="4,5,6,7,8,9,10,11,12,13,14,15" class="xyz">All</a></li>
  <li><a href="#" data-slug="10" class="xyz">category1</a></li>
  <li><a href="#" data-slug="12" class="xyz">category2</a></li>
  <li><a href="#" data-slug="15" class="xyz">category3</a></li>
  <li><a href="#" data-slug="9" class="xyz">category4</a></li>
  <li><a href="#" data-slug="4" class="xyz">category5</a></li>
  <li><a href="#" data-slug="11" class="xyz">category6</a></li>
  <li><a href="#" data-slug="13" class="xyz">category7</a></li>
  <li><a href="#" data-slug="8" class="xyz">category8</a></li>
  <li><a href="#" data-slug="7" class="xyz">category9</a></li>
</ul>