Uiua, 236 bytes

G←&p$"Song: _\nArtist: _"
F←G⨬("Batman Theme""Neal Hefti"G"Na Na Hey Hey Kiss Him Goodbye""Steam"|"Africa""Toto"|"Katamari Damacy""Yuu Miyake"|"Hey Jude""The Beatles"|"Land of 1000 Dances""Wilson Picket")↧4⍥⋅1:⊙↥⊃-<8÷3:¬⊃≍⧻↯△,"NA "⊂⊙@ ⌵

Try it: Uiua pad

05AB1E, 148 bytes

l#„naQW*O5Ý8+@OI5£“‹…0Toto
߃›Ì0Neal Hefti0ÿ¤·¤··—„š‚¿bye0ÁÜ

KatamariÊÖacy0Yuu Miyake
¤· Jude0€€ÊÄ
ˆÑ€‚ 2–›s0¦‹šèett“¶¡0δ¡2₄:¬2ǝ„ŽŸŒá#ÞrèðδÛø„: ý»™

Try it online or verify some more test cases.

Explanation:

l            # Convert the (implicit) input-string to lowercase
 #           # Split it on spaces (if there are any)
  „naQ       # Check for each word if it's equal to "na" (1 if truthy; 0 if falsey)
      W      # Push its minimum, without popping the list itself
       *     # Multiply that to all integers
             # (if any word wasn't "na", the entire list now only contains 0s)
        O    # Sum this list to get the amount of "na"s
5Ý           # Push the list [0,1,2,3,4,5]
  8+         # Add 8 to each: [8,9,10,11,12,13]
    @        # Check for each if the sum is larger than or equal to this value
             # (1 if sum>=n, 0 if sum<n)
     O       # Sum to get the amount of truthy values
I            # Push the input-string
 5£          # Pop and only leave its first 5characters (if it's a valid string,
             # this will be "na na" - with variable casing)
   “‹…0Toto
    ߃›Ì0Neal Hefti0ÿ¤·¤··—„š‚¿bye0ÁÜ
    
    KatamariÊÖacy0Yuu Miyake
    ¤· Jude0€€ÊÄ
    ˆÑ€‚ 2–›s0¦‹šèett“
             # Push dictionary string "africa0 Toto\nbatman theme0Neal Hefti0ÿ hey hey kiss him goodbye0 steam\n\nKatamari damarcy0Yuu Miyake\nhey Jude0 the beatles\nland of 2 dances0 wilson pickett",
             # where the `ÿ` is automatically replaced with the 5-char string
¶¡           # Split this string on newlines
  0δ¡        # And then split each inner string on 0s
             #  [["africa"," Toto"],
             #   ["batman theme","Neal Hefti","na na hey hey kiss him goodbye"," steam"],
             #   [],
             #   ["Katamari damarcy","Yuu Miyake"],
             #   ["hey Jude"," the beatles"],
             #   ["land of 2 dances"," wilson pickett"]]
     2₄:     # Replace the 2 with 1000
        ¬    # Get the first pair (without popping): ["africa"," Toto"]
         2ǝ  # Insert it at (0-based) index 2, replacing the empty list
„ŽŸŒá        # Push dictionary string "song artist"
     #       # Split it on spaces: ["song","artist"]
      Þ      # Cycle this list infinitely: ["song","artist","song","artist",...]
r            # Reverse the values on the stack
 è           # Modulair 0-based index the sum of truthy values into the list of lists of
             # artist(s)/song(s), so 6 will wrap back to the first item
   δ         # Map over each string inside each inner list:
  ð Û        #  And trim all leading spaces
     ø       # Create pairs with the infinitely cycled list, where it will only create
             # as many pairs as the smallest list (so either 2 or 4 in this case)
      „: ý   # Join each inner pair with ": " delimiter
          »  # Then join everything by newlines
           ™ # And finally titlecase each word in the string
             # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to use the dictionary?) to understand why “‹…0Toto ߃›Ì0Neal Hefti0ÿ¤·¤··—„š‚¿bye0ÁÜ\n\nKatamariÊÖacy0Yuu Miyake\n¤· Jude0€€ÊÄ\nˆÑ€‚ 2–›s0¦‹šèett“ is "africa0 Toto\nbatman theme0Neal Hefti0ÿ hey hey kiss him goodbye0 steam\n\nKatamari damarcy0Yuu Miyake\nhey Jude0 the beatles\nland of 2 dances0 wilson pickett" and „ŽŸŒá is "song artist".

UNIX Shell, 394 bytes

uudecode -p<<<'begin-base64 0 -
/Td6WFoAAATm1rRGAgAhARwAAAAQz1jM4AE9AIRdACmbycaLOYv90Azj3HBohRZGa6a5FikeJU+8JbGlB4f9wmi2aQ+mn81aypMRM4nEKPxW439Z2C4WfGeyrREjk427H1GrCRUMHdth+9lVBDiPfCaD8WpStyS0MtJenHKB+tou8rD9INq0yw9IPXuQe7zLM3p14ZDFO8UoJp66scd4bKQAAACSwUb7ERvesgABoAG+AgAARAEAGbHEZ/sCAAAAAARZWg==
===='|unxz|sed -n $#s/,/\\n/gp|grep .||echo $'Song: Land Of 1000 Dances\nArtist: Wilson Pickett'

Test:

; sh $THE_FILE na na na na na na na
Song: Batman Theme
Artist: Neil Hefti

Song: Na Na Hey Kiss Him Goodbye
Artist: Steam

Probably could be optimized, but I just liked this idea TBH :)

C (gcc), 403 395 370 365 364 362 bytes

-8 -5 -1 = -14 bytes thanks to ceilingcat

Pretty much as straight-forward as can be.

f(char*s){int*a[]={"Neal Hefti","Steam","Yuu Miyake","The Beatles","Wilson Pickett","Toto","Batman Theme","Na Na Hey Hey Kiss Him Goodbye","Katamari Damacy","Hey Jude","Land Of 1000 Dances","Africa"},i,l=0,j=1;for(;*s;s+=3-!s[2])i=(*s|32)^'n'|(s[1]|32)^97|s[2]>32,l++;for(i=i?5:l^8?l^10?l^11?l>11?4:5:3:2:j++;j--;)printf("Song: %s\nArtist: %s\n",a[6+i--],a[i]);}

Try it online!

Perl 5, 312 292 bytes

$_=lc<>;$n="(na ?)";/^(na ){7}na$|(na ){9,}na/ or$_="%Africa&Toto";s/$n{12,}/%Land Of 1000 Dances&Wilson Pickett/;s/$n{11}/%Hey Jude&The Beatles/;s/$n{10}/%Katamari Damacy&Yuu Miyake/;s/$n{8}/%Batman Theme&Neal Hefti\n%Na Na Hey Hey Kiss Him Goodbye&Steam/;s/&/\nArtist: /g;s/%/Song: /g;print

Try it online!

Ungolfed:

$_ = lc <STDIN>;
$_ =~ /^(na ){7}na$|(na ){9,}na/ or $_ = "%Africa&Toto";
$_ =~ s/(na ?){12,}/%Land Of 1000 Dances&Wilson Pickett/;
$_ =~ s/(na ?){11}/%Hey Jude&The Beatles/;
$_ =~ s/(na ?){10}/%Katamari Damacy&Yuu Miyake/;
$_ =~ s/(na ?){8}/%Batman Theme&Neal Hefti\n%Na Na Hey Hey Kiss Him Goodbye&Steam/;
$_ =~ s/&/\nArtist: /g;
$_ =~ s/%/Song: /g;
print $_

Perl 5 -pa, 248 bytes

$_=/^(na ?)+$/&&(@F==8?",Batman Theme;Neal Hefti,Na Na Hey Hey Kiss Him Goodbye;Steam":@F==10?"Katamari Damacy;Yuu Miyake":@F==11?",Hey Jude;The Beatles":@F>11?",Land Of 1000 Dances;Wilson Pickett":0)||",Africa;Toto";s/;/
Artist: /gm;s/,/
Song: /gm

Try it online!

Rust, 501 477 bytes

fn main(){let(mut i,mut n)=(String::new(),0);let(s,a);std::io::stdin().read_line(&mut i);i=i.trim().to_lowercase();let o=i.split(" ");for w in o{if w!="na"{n=0;break}else{n+=1}}match n{8=>{println!("Song: Batman Theme\nArtist: Neal Hefti");s="Na Na Hey Hey Kiss Him Goodbye";a="Steam"}10=>{s="Katamari Damacy";a="Yuu Miyake"}11=>{s="Hey Jude";a="The Beatles"}_=>{if n>=12{s="Land Of 1000 Dances";a="Wilson Pickett"}else{s="Africa";a="Toto"}}}print!("Song: {}\nArtist: {}",s,a)}

Ungolfed

fn main() {
    let (mut input_string, mut na_counter) = (String::new(), 0);
    let (song_name, artist_name);

    std::io::stdin().read_line(&mut input_string);
    input_string = input_string.trim().to_lowercase();
    let output = input_string.split(" ");

    for word in output {
        if word != "na" {
            na_counter = 0;
            break;
        } else {
            na_counter += 1;
        }
    }

    match na_counter {
        8 => {
            println!("Song: Batman Theme\nArtist: Neal Hefti");
            song_name = "Na Na Hey Hey Kiss Him Goodbye";
            artist_name = "Steam";
        }
        10 => {
            song_name = "Katamari Damacy";
            artist_name = "Yuu Miyake";
        }
        11 => {
            song_name = "Hey Jude";
            artist_name = "The Beatles";
        }
        _ => {
            if na_counter >= 12 {
                song_name = "Land Of 1000 Dances";
                artist_name = "Wilson Pickett";
            } else {
                song_name = "Africa";
                artist_name = "Toto";
            }
        }
    }

    print!("Song: {}\nArtist: {}", song_name, artist_name);
}

Edit: removed an unnecessary to_string and type annotations

Java 8, 353 bytes

s->{int n=s.split(" ").length,b=s.matches("(na ?)+")?1:0;s="Africa";return"Song: "+(b>0?n<8?s:n<9?"Batman Theme\nArtist: Neal Hefti\nSong: Na Na Hey Hey Kiss Him Goodbye":n>11?"Land of 1000 Dances":n>10?"Hey Jude":n>9?"Katamari Damacy":"":s)+"\nArtist: "+(b>0?n<8?"Toto":n<9?"Steam":n>11?"Wilson Pickett":n>10?"The Beatles":n>9?"Yuu Miyake":"":"Toto");}

Explanation:

Try it online.

s->{                             // Method with String as both parameter and return-type
  int n=s.split(" ").length,     //  The amount of words when split by spaces
      b=s.matches("(na ?)+")?1:0;//  Whether the input matches the regex "^(na ?)+$"
  s="Africa";                    //  Set the input we no longer need to "Africa"
  return"Song: "                 //  Return "Song: "
    +(b>0?                       //   +If the input matched the regex:
       n<8?                      //     If there are less than 8 "na"'s: 
        s                        //      Append "Africa"
       :n<9?                     //     Else-if there are exactly 8 "na"'s:
        "Batman Theme\nArtist: Neal Hefti\nSong: Na Na Hey Hey Kiss Him Goodbye"
                                 //      Append the String above
       :n>11?                    //     Else-if there are 12 or more "na"'s:
        "Land of 1000 Dances"    //      Append "Land of 1000 Dances"
       :n>10?                    //     Else-if there are exactly 11 "na"'s:
        "Hey Jude"               //      Append "Hey Jude"
       :n>9?                     //     Else-if there are exactly 10 "na"'s:
        "Katamari Damacy"        //      Append "Katamari Damacy"
       :                         //     Else (there are exactly 9 "na"'s):
        ""                       //      Append nothing
      :                          //    Else:
       s)                        //     Append "Africa"
    +"\nArtist: "                //   +Append a new-line and "Artist: "
    +(b>0?                       //   +If the input matched the regex:
       n<8?                      //     If there are less than 8 "na"'s:
        "Toto"                   //      Append "Toto"
       :n<9?                     //     Else-if there are exactly 8 "na"'s:
        "Steam"                  //      Append "Steam"
       :n>11?                    //     Else-if there are 12 or more "na"'s:
        "Wilson Pickett"         //      Append "Wilson Pickett"
       :n>10?                    //     Else-if there are exactly 11 "na"'s:
        "The Beatles"            //      Append "The Beatles"
       :n>9?                     //     Else-if there are exactly 10 "na"'s:
        "Yuu Miyake"             //      Append "Yuu Miyake"
       :                         //     Else (there are exactly 9 "na"'s):
        ""                       //      Append nothing
      :                          //    Else:
       "Toto");}                 //     Append "Toto"

Julia, 325 bytes

Probably could be golfed further.

p(s,a)=println("Song: $s\nArtist: $a");ismatch(r"^(na )*na$",ARGS[1])&&(c=length(split(ARGS[1],"na"))-1)==8?(p("Batman Theme","Neal Hefti"),p("Na Na Hey Hey Kiss Him Goodbye","Steam")):c==10?p("Katamari Damacy","Yuu Miyake"):c==11?p("Hey Jude","The Beatles"):c>=12?p("Land Of 1000 Dances","Wilson Pickett"):p("Africa","Toto")

PowerShell, 278 bytes

• Can handle any amount of whitespace
• No regex whatsoever!
• Implicit typecasting FTW!

@{8='Batman Theme/Neal Hefti','Na Na Hey Hey Kiss Him Goodbye/Steam'
10='Katamari Damacy/Yuu Miyake'
11='Hey Jude/The Beatles'
12='Land Of 1000 Dances/Wilson Pickett'}[[math]::Min($args.Count*!($args|?{$_-ne'na'}),12)]|%{'Song: {0}
Artist: {1}'-f($_+'Africa/Toto'*!$_-split'/')}

Ungolfed

@{8='Batman Theme/Neal Hefti','Na Na Hey Hey Kiss Him Goodbye/Steam' # array
10='Katamari Damacy/Yuu Miyake'
11='Hey Jude/The Beatles'
12='Land Of 1000 Dances/Wilson Pickett'} # Hashtable of songs
[   # Get value by key from hashtable
    # If key is invalid, silently return null value

    [math]::Min( # Clamp max value to 12
        $args.Count* # Multiply count of argumens
                     # true/false will be cast to 1/0
            ! # Negate result of expression
              # Will cast empty array to 'false'
              # and non-empty array to 'true'
            (
                # Return non-empty array if input arguments
                # contain anything other than 'na'
                $args | Where-Object {$_ -ne 'na'} 
            ),
        12
    )
] | ForEach-Object { # Send value from hashtable down the pipeline,
                     # This allows to process arrays in hasthable values
    'Song: {0}
    Artist: {1}' -f ( # Format string
        $_+ # Add to current pipeline variable
            'Africa/Toto'*!$_ # If pipeline variable is empty,
                              # then add default song to it
                              # Example: 'Test'*1 = 'Test'
                              #          'Test'*0 = null
        -split '/' # Split string to array for Format operator
    )
}

Usage

PS > .\WhatSong.ps1 na na na na na na na na
Song: Batman Theme
Artist: Neal Hefti
Song: Na Na Hey Hey Kiss Him Goodbye
Artist: Steam

PS > .\WhatSong.ps1 Na na na na na na na na na Na
Song: Katamari Damacy
Artist: Yuu Miyake

PS > .\WhatSong.ps1 Na na na na na na na na na BanaNa
Song: Africa
Artist: Toto

Python 453 440 406 380 bytes

EDIT: Thanks to Cyoce for reducing 13 bytes!

EDIT: Thanks again to Cyoce!

EDIT: Thanks to RainerP. for helping me imrpove the algorithm on certain invalid cases.

This is a rough draft of a Python program. I believe it can be definitely golfed, maybe to 300-400 bytes. But will work on that soon.

f=0
S='Song:'
A='\nArtist:'
l="Batman Theme,Neal Hefti,Na Na Hey Kiss Him Goodbye,Steam,Katamari Damacy,Yuu Miyake,Hey Jude,Beatles,Land of the 1000 Dances,Wilson Pickett,Africa,Toto".split(',')
s=raw_input().lower()+" "
n=s.count("na ")
n*=n*3==len(s)
if n>11:f=8
if n==10:f=4
if n==11:f=6
if n<8or n==9:f=10
if f:print S+l[f]+A+l[f+1]
else:print S+l[0]+A+l[1]+"\n"+S+l[2]+A+l[3]

Try here!

sh + coreutils, 290

Albeit longer than my other submission, this one is straightforward and pretty much ungolfed, so i included it anyway.

grep -Ei "^na( na)*$"|wc -w|awk '{s="Song: ";a="\nArtist: ";p=s"Africa"a"Toto"}$1==8{p=s"Batman Theme"a"Neal Hefti\n"s"Na Na Hey Hey Kiss Him Goodbye"a"Steam"}$1>9{p=s"Katamari Damacy"a"Yuu Miyake"}$1>10{p=s"Hey Jude"a"The Beatles"}$1>11{p=s"Land Of 1000 Dances"a"Wilson Pickett"}{print p}'

How it works:

If the input is valid, print it as is. If not, print nothing.

grep -Ei "^na( na)*$"

Count the words.

wc -w

Simple look up table, Song: and Artist: are kept in variables.

awk '
    {s="Song: ";a="\nArtist: ";p=s"Africa"a"Toto"}
    $1==8{p=s"Batman Theme"a"Neal Hefti\n"s"Na Na Hey Hey Kiss Him Goodbye"a"Steam"}
    $1>9{p=s"Katamari Damacy"a"Yuu Miyake"}
    $1>10{p=s"Hey Jude"a"The Beatles"}
    $1>11{p=s"Land Of 1000 Dances"a"Wilson Pickett"}
    {print p}
'

JavaScript (ES6), 276 bytes

alert(`Song: `+([,`Batman Theme,Neal Hefti
Song: Na Na Hey Hey Kiss Him Goodbye,Steam`,,`Katamari Damacy,Yuu Miyake`,`Hey Jude,The Beatles`,`Land Of 1000 Dances,Wilson Pickett`][+prompt(i=0).replace(/na( |$)/gi,_=>++i)&&(i>11?4:i-7)]||`Africa,Toto`).replace(/,/g,`
Artist: `))

Explanation

Input can optionally contain one trailing space.

alert(                 // output the result
  `Song: `+([          // insert the "Song:" label
      ,                // set the first element to undefined in case input is empty

      // Songs
      `Batman Theme,Neal Hefti
Song: Na Na Hey Hey Kiss Him Goodbye,Steam`,
      ,
      `Katamari Damacy,Yuu Miyake`,
      `Hey Jude,The Beatles`,
      `Land Of 1000 Dances,Wilson Pickett`

    ][
      +                // if the input string was made up only of "na"s, the replace would
                       //     return a string containing only digits, making this return a
                       //     number (true), but if not, this would return NaN (false)
        prompt(        // get the input string
          i=0          // i = number of "na"s in input string
        ).replace(     // replace each "na" with a number
          /na( |$)/gi, // find each "na"
          _=>++i       // keep count of the "na"s and replace with a (non-zero) number
        )
      &&(i>11?4:i-7)   // select the song based on the number of "na"s
    ]
      ||`Africa,Toto`  // default to Africa
  ).replace(/,/g,`
Artist: `)             // insert the "Artist:" label
)

Test

var prompt = () => input.value;
var alert = (text) => result.textContent = text;
var solution = () => {

alert(`Song: `+([,`Batman Theme,Neal Hefti
Song: Na Na Hey Hey Kiss Him Goodbye,Steam`,,`Katamari Damacy,Yuu Miyake`,`Hey Jude,The Beatles`,`Land Of 1000 Dances,Wilson Pickett`][+prompt(i=0).replace(/na( |$)/gi,_=>++i)&&(i>11?4:i-7)]||`Africa,Toto`).replace(/,/g,`
Artist: `))

}

<input type="text" id="input" value="na na Na na NA na na nA" />
<button onclick="solution()">Go</button>
<pre id="result"></pre>

Retina, 242

Try it online!

iG`^na( na)*$
iM`na
m`^8$
>Batman Theme,Neal Hefti$n>Na Na Hey Hey Kiss Him Goodbye,Steam
m`^10$
>Katamari Damacy,Yuu Miyake
m`^11$
>Hey Jude,The Beatles
[0-9].+
>Land Of 1000 Dances,Wilson Pickett
m`^[0-9]
>Africa,Toto
>
Song: 
,
$nArtist: 

How it works:

IgnoreCase flag + Grep mode flag + Regex ^na( na)*$. If the input is valid, print it as is. If not, print nothing.

iG`^na( na)*$

IgnoreCase flag + Match mode flag + Regex na. Count the "na"s and print the number.

iM`na

If the string is exactly "8", replace by the second line.

m`^8$
>Batman Theme,Neal Hefti$n>Na Na Hey Hey Kiss Him Goodbye,Steam

If the string is exactly "10", replace by the second line.

m`^10$
>Katamari Damacy,Yuu Miyake

If the string is exactly "11", replace by the second line.

m`^11$
>Hey Jude,The Beatles

If the string matches [0-9].+, replace by the second line. This is neither true for single digit numbers, 10 and 11 as they already have been repaced nor any of the above replacement strings.

[0-9].+
>Land Of 1000 Dances,Wilson Pickett

If none of the above matched, the string still starts with a number. Default to Toto, Africa.

m`^[0-9]
>Africa,Toto

Replace the placeholders > and , by Song: and Artist:.

>
Song: 
,
$nArtist: