In amateur practice "<call> calling <call>" is sometimes used for phone, especially UHF/VHF, perhaps out of the ARRL's stated preference for communications being clear and easy to understand without reliance on jargon or convention.
However, especially on other modes and even with phone in most cases, the standard is "<call> <call>". This is more or less derived from morse operating practice where the prosign "DE" means "this is" or "from," and the typical way of calling another station was "<call> DE <call>" (or perhaps "<call> DE <call> GA"). Naturally the DE was dropped in many cases and it became just the two calls in sequence with an implied DE.
There is actually no regulatory requirement to state call sign at the beginning of a conversation, although it's standard to because, well, it's nice to know who you're talking to. FCC regulations do require each party to state their call sign at the end of a conversation, usually as "<call> SK" in the case of morse or "<call> clear" in the case of phone, although I'd say use of the "clear" proword is somewhat more variable. I've always had a certain dislike for "we'll be clear" as this is a bit confusing to newcomers, less so than "clear on your final" although that seems more formal.
I assume that, like most radio conventions, this originated in naval use, as the convention is the same in at least aviation and public safety.