Source of the exact phrase "Absence makes the heart grow fonder"
Linda Flavell & Roger Flavell, Dictionary of Proverbs and Their Origins (1993) offers this background on the phrase:
This [“absence makes the heart grow fonder”] is a line from a song ISLE OF BEAUTY (before 1839) by Thomas Haynes Bayly. It was Bayly who popularized the words, but [Burton] Stevenson [in Book of Proverbs, Maxims, and Famous Phrases (1947)] says they are not of his inspiration, being originally the first line of an anonymous poem which appeared in Davison’s POETICAL RAPSODY of 1602.
In fact, the full song (and piano score) for “Isle of Beauty, Fare Thee Well,” credited to T. H. Bayly, appears in The New York Mirror of June 4, 1831. Here is the complete third verse:
When the waves are round me breaking,/As I pace the deck alone./And my eyes in vain are seeking/Some green leaf to rest upon ;/What would I not give to wander/Where my old companions dwell?/Absence makes the heart grow fonder./Isle of Beauty, “fare thee well!"
[[Update: I've found references to Bayly's lyric, dating to 1826 and perhaps 1825; see "Pre-1831 published references to Bayly's 'Isle of Beauty,'" the final subsection of my answer, below.]]
I checked several online versions of Davison's Poetical Rhapsody—which differ somewhat in the number of poems and song lyrics they contain—and couldn’t find the phrase “absence makes the heart grow fonder” in any of them. I don’t know what to make of Stevenson’s assertion that the phrase originated in the Poetical Rhapsody; several proverb researchers express respect for his scholarship. Ultimately, though, the absence of “Absence makes the heart grown fonder” from the Davison collections that I’ve seen and the absence of the phrase from the various early collection of proverbs and sayings that I’ve consulted leave me doubtful about his claim.
In John Ray, A Compleat Collection of Proverbs, fourth edition (1768) (see page 281), for example, the only proverb incorporating the word absence is "Absence is a shroe [that is, ‘shrew’]." And even as late as Henry Bohn, A Hand-Book of Proverbs (1875), the only two proverbs starting with absence are "Absence cools moderate passions, but inflames violent ones," and "Absence sharpens love, presence strengthens it." The first collection I’ve found that includes “Absence makes the heart grow fonder is Robert Christy, Proverbs, Maxims and Phrases of All Ages (1887), which lists "J. H. Bailey" as the source of the phrase.
Earlier English phrases that express the same general idea
Flavell & Flavell does identify several quotations that (in the authors’ view) express similar sentiments:
In Shakespeare’s OTHELLO (1604), Desdemona confesses I dote upon his very absence (Act I, scene ii); in FAMILIAR LETTERS (1650) James Howell discloses that Distance sometimes endears friendship, and absence sweeteneth it. La Rochefoucauld quotes a French proverb which says that Friends agree best at a distance (MAXIMES, 1665) while Rofer de Bussy-Rabutin writes: Absence is to love what wind is to fire; it puts out the little, it kindles the great (MAXIMES D’AMOUR, 1666).
The (unacknowledged) source of these citations appears to be William Walsh, Handy-Book of Literary Curiosities (1892), which also offers quotes from Charles Hopkins, “To C. C.” [written by 1699] (“I find that absence still increases love”) and Frederick W. Thomas, “Absence Conquers Love” [published between 1830 and 1833] (“’Tis said that absence conquers love,/But, oh, believe it not!/I’ve tried, alas,! Its power to prove,/But thou art not forgot”). Unfortunately, both Walsh and Flavell & Flavell appear to have gotten their Shakespeare wrong; as Mari-Lou A observes in her question above, the line is from The Merchant of Venice, and involves quite the opposite of fondness at any distance:
Portia. If I live to be as old as Sibylla, I will die as chaste as Diana, unless I be obtained by the manner of my father’s will. I am glad this parcel of wooers are so reasonable ; for there is not one among them but I dote on his very absence, and I wish them a fair departure.
The Howell quotation, by the way, appears in this collection in a letter (to Dan. Caldwell, esq.) from Amsterdam, dated 10 April 1619, when Howell was 25 years old.
A very early (Latin) precursor, and the Franklin complication
Martin Manser, The Facts on File Dictionary of Proverbs (2002) mistakenly reports that the proverb “Absence makes the heart grow fonder” was “first recorded c. 1850,” but this reference work does provide an interesting (and very relevant) instance of the same idea in Sextus Propertius, who died in A.D. 2:
“semper in absentes felicior aestus amantes ["passion is always warmer toward absent lovers]."
Gregory Titelman, Random House Dictionary of America’s Popular Proverbs and Sayings, second edition (2000) likewise cites the Sextus Propertius quotation, and then offers this rather mysterious comment:
First cited in the United States in 1755 in Papers of Benjamin Franklin.
If the idea here is that Franklin was the first to quote Sextus Propertius’s Latin phrase in the United States, the claim seems both dubious and rather beside the point; if the idea is that Franklin devised the wording “Absence makes the heart grow fonder," he would certainly have precedence over Bayly—but at the online Papers of Benjamin Franklin site, I couldn't find any exact matches for either "absence makes" or "absentes felicior."
Unless someone can confirm the phrase’s appearance in Davison’s Poetical Rhapsody or Franklin’s Papers or some as yet unidentified source, it seems to me, Thomas H. Bayly has the strongest claim to having crafted the wording “Absence makes the heart grow fonder,” which appeared in print by June 4, 1831.
UPDATE (9/22/14): The Franklin mystery unraveled
I found a second, more specific reference to the Franklin Papers in Bartlett J. Whiting, Early American Proverbs and Proverbial Phrases (1977), which lists collected aphorisms under numerous generalized headings. Under the heading "Absence increases affection," Whiting offers the following items:
1755 CRay in Franklin Papers 6.96: For Absence rather increases than lesens my affections. 1775 MWard in Ward Correspondence 50: How absenc endears a beloved object to us. 1783 Mrs. TBurr in Burr Memoirs 1,244: Some think absense tends to increase affection; the greater part that it wears it away. 1797 Foster Coquette 149: I think you formerly remarked that absence served but to height real love.
Sure enough, the Franklin Papers site includes this fuller observation by Catharine Ray, in a letter to Benjamin Franklin dated June 28, 1755:
Dear, Dear Sir,
Excues my writeing when I tell you it is the great regard I have for you will not let me be Silent, for Absence rather increasis than lesens my affections then, my not receiveing one line from you in answer to 3 of my last letters March the 3d and 31st and April the 28th gives me a Vast deal of uneasiness and occation’d many tears, for Suerly I have wrote too much and you are affronted with me or have not received my letters in which I have Said a thousand things that nothing Should have tempted me to [have] Said to any body els for I knew they wold be Safe with you. I’ll only beg the favor of one line. What is become of my letters? Tel me you are well and forgive me and love me one thousandth Part So well as I do you and then I will be Contented and Promise an amendment.
Evidently, the effect of absence on affection was something that Ms. Ray had experienced personally. On the other hand, she didn't use the phrase "Absence makes the heart grow fonder," and presumably Franklin didn't publicize her letter to the wider world.
Other Colonial American and early U.S. predecessors
The Ward quote from 1775 appears in a letter dated June 19, 1775, in Rhode Island Historical Society, Correspondence of Governor Samuel Ward, May 1775–March 1776 (1952) [snippet]:
how absenc endears a beloved object to us; its almost Like burying them ; we forget all their faults and Every thing Disagreable, on the other hand every Little act of kindness which then Pass'd unnoticed
Google Books does not contain any other reference to the Burr quotation, but the Foster quotation appears in Hannah Webster Foster, The Coquette (1797), an epistolary novel:
I [Eliza Wharton] think you [the Rev. J. Boyer] formerly remarked that absence served but to heighten real love. This I find by experience. Need I blush to declare these sentiments, when occasion like this calls for the avowal? I will go even further, and offer you that heart which you once prized, that hand which you once solicited. The sentiments of affection which you then cultivated, though suppressed, I flatter myself are not wholly obliterated. Suffer me, then, to rekindle the latent flame, to revive that friendship and tenderness which I have so foolishly neglected. The endeavor of my future life shall be to reward your benevolence, and perhaps we may yet be happy together.
According to its Wikipedia article, The Coquette "was one of the best-selling novels of its time and was reprinted eight times between 1824 and 1828." That would make it a far stronger candidate than the private letters of Franklin, Ward, or Burr to have influenced the sentiments that T. H. Bayly expressed in his 1826 (or earlier) song "Isle of Beauty." And "absence serves but to heighten real love" is very much of a piece with "absence makes the heart grow fonder."
Meanwhile, by way of illustrating that the opposing "out of sight, out of mind" school has a long pedigree of its own, Whiting offers these specimens under the heading "Absence is a cure of love":
1709 Wylllys Papers 360: Distance and Absence may cure a passion that may be greatly detrimental to my wife's onely Son. 1781 Baldwin Life and Letters 56: Tho absence they say is a general cure for love.
Under the circumstances, it's not surprising that some people have sought to reconcile the rival schools of thought on absence by cobbling together (as cited above in Bohn's Hand-Book of Proverbs) the saying "Absence cools moderate passions, but inflames violent ones." That saying is adaptable to every situation—since if the heart grows fonder, it proves the violence of the original passions, but if the formerly beloved departs out of mind, it proves their moderateness—and so represents a kind of perfection of proverbial wisdom.
Pre-1831 published references to Bayly's "Isle of Beauty"
One of a number of earlier mentions of the title “Isle of Beauty, Fair Thee Well” occurs in The Harmonicon: A Journal of Music (1829), which identifies the song as “Romanza, " Isle of Beauty, fare thee well !" the melody by C. S. Whitmore, Esq., with an Introduction and Variations by G. Kiallmark,” and offers this rather sour assessment of the tune:
The fatiguing sameness of key in the third of these [new songs, namely “Isle of Beauty”], and the absence of anything in the shape of new ideas, have rendered the playing it through a very tedious task indeed.
That this refers to the song with lyrics by Bayly is evident from this entry in Royal Lady’s Magazine, and Archives of the Court of St. James (September 1831):
Isle of Beauty, Fare Thee Well, by F. H. Bayly, Esq. The melody composed by C. S. Whitmore, Esq. The Symphonies and Accompaniments by T. A. Rawlings.
No wonder this song has reached a fourth edition, it richly deserves it, and we have no doubt it will soon reach as many more. The melody is not very original, but it is full of expression and feeling, such as we meet with in so many of Mozart’s little airs.
The song is noted even earlier in the “New Music” section of The Monthly Review or British Register of Literature, Sciences, and Belles-Letters (May 1826):
“Songs to Rosa.” The Poetry of Thos. H. Bayley, Esq, with Symphonies and Accompaniments by T.A. Rawlings. 2s. ... “Isle of Beauty,” if we rightly understand the editor, is the composition of an amateur, C. S. Whitemore, Rsq. ; it is a truly elegant strain, and well adapted to the expression of the poesy.
And Google Books finds a nonpreviewable volume (which it dates to 1825) bearing this title:
“Isle of Beauty. [By T.H. Bayly.] Bonnie Breist Knots. To which is Added, The Braes Aboon Bonaw. My Luve's in Germany. Sweet Jessie O'the Dell. The Battle of Hohenlinden. [Songs.].”
Evidently the various lyrics in “Songs to Rosa” were popular enough quickly enough to inspire satirical comments such as this one from “The Dunciad of To-day, “ in The Star Chamber (May 10, 1826):
And happy he, whose nightly fare’s no worse/Than BISHOP’s Melodies, and BAILY’s Verse ;/Though puff’d Aladdin was a scurvy trick,/And “Songs to Rosa” makes me very sick.
The “Songs to Rosa” collection seems to have been published in England in early 1826. An advertisement for it appears in The London Literary Gazette of March 18, 1826, followed by an enthusiastic review of the collection in the April 1, 1826, issue of the same periodical under the head “New Publications.” The Harmonicon reviews it, too, in June 1826, with considerably more kindness than its critic exhibited when revisiting “Isle of Beauty” three years later.