Hand them a period and a paragraph mark, please
Found this rather tortured construction the other day in the Wall Street Journal, of all places (a still well-edited paper, but not nearly so as in the past):

Mr. Okrent said of the editors' article: "It's a pretty remarkable statement," adding, "It's easy to apologize for spelling someone's name wrong," Mr. Okrent said. "It's much harder to apologize for letting readers down on an important story."

Such run-on attribution sentences crop up more, it seems, these days, and I'm not sure why. Simple solution: get rid of the lame "adding," which is overused by journalists anyhow. Stick a period at the end of the first quote, paragraph, and pick up the second quote (with the quote mark necessary because of the following attribution -- even if the two quotes actually came back to back).