Batman needs to start throwing roses. I mean, he's already got Tuxedo Kamen's quick disappearance thing down, so all he really needs are the roses.
Also I had assumed that he recognized J'onn because of what the name means ("spirit of fire") rather than because of who the name belongs to. But I really prefer the Sailor Moon theory.