Looks like the sport plus database can actually handle 6k songs. They are probably stating 4k due to capacity of 16GB.
http://kb.sandisk.com/app/answers/detail/a_id/20092/