Melville's use of game = plucky is pretty dated today, but some people still use the word with a somewhat different (and later) nuance as in I'm game = I'm up for it / willing [to participate in something].
Google Books has over 100 instances of his game heart with the stout / resolute / brave sense.
Melville was probably influenced by the equally dated his heart of oak (over 1800 written instances in Google Books), which has essentially the same meaning.
There's no obvious reason1 why the specific combinations heart of oak and game heart should have become idiomatically established in preference to oak heart and heart of game. Melville certainly wasn't breaking any rules of grammar by choosing the latter - it's just that it was "less idiomatic" even back in 1849 when he was writing Mardi, and A Voyage Thither.
Etymologically speaking, adjectival game here derives from the noun game meaning fun, sport, amusement. It's only "indirectly" related to the derivative game = animals hunted for sport, though of course Melville may have intended his readers to make that connection.
1 But I would point out that elsewhere in the book, Melville uses heart of grace. I don't know how to articulate exactly what "grammatical rule" prevents us using the form grace heart, but that one is so jarring to me I feel sure there must be one.