It's been hours and I've reloaded, quit, warped, etc multiple times but still no dice. Any clue on where or when his tombstone appears?
As of current knowledge the best and most efficient way of making tombstones appear is by Quit/Reloading until they appear. I have in personal experience had NPC's come back anywhere from the first reload (immediately after killing) to the fourth (also immediately after killing). Also be aware that the Tombstone locations do not completely correspond to the locations you killed them, and you may have to search around to all locations the NPC goes to.
He has two locations:
- No-Man's Wharf
His tombstone in Majula appears quite fast (a couple of reloads for me), but I killed him in Majula.
I don't know what happens when you kill him in No-Man's Wharf: where his tombstone is going to appear.
This is not uncommon for this to occur for any of the NPC's, it's just more common for some rather than others. The general consensus is to quit and reload, wait up to 2 in-game hours (leave the area, don't just go AFK in front of the dead NPC), then return.
Also it is entirely possible that if you killed him in No-Man's Wharf, his tombstone could appear in Majula, as that is his final meeting place. Other characters that this occurs with are Ornifex (You find her in the Shaded Ruins, and the tombstone can be located in her shop in Brightstone Tseldora), and (I believe) Licia of Lindelt.
EDIT: His grave appears in Majula
It differs depending on the NPC that you killed, for Carhillion it's not currently listed (at time of posting)
I believe there is no tombstone for Carhilion, the only tombstone that can appear is when you kill Licia of Lindeldt. I assume this mechanic was introduced since the game contains an item that allows you to invade and kill Licia.
EDIT: I stand corrected, here's a link to Fextralife Dark Souls 2 Wiki containing a page mentioning that there's a tombstone for every important NPC including merchants. LINK