C (gcc), 403 bytes
Pretty much as straight-forward as can be.
f(char*s){int i,v=1,l=(strlen(s)+1)/3,j=1;char*a[]={"Neal Hefti","Steam","Yuu Miyake","The Beatles","Wilson Pickett","Toto"},*S[]={"Batman Theme","Na Na Hey Hey Kiss Him Goodbye","Katamari Damacy","Hey Jude","Land Of 1000 Dances","Africa"};for(;*s;s+=s[2]?3:2)(*s|32)^'n'|(s[1]|32)^97|(s[2]^32&&s[2])?v=0:0;for(i=v?l==8?j=2,1:l^10?l^11?l>11?4:5:3:2:5;j--;i--)printf("Song: %s\nArtist: %s\n",S[i],a[i]);}