Hiya

Yes, it comes from billyboy's The Tempest:

"Full fathom five thy father lies
Of his bones are coral made
Those are pearls that were his eyes
Nothing of him that doth fade
But doth suffer a sea-change
Into something rich and strange."

The general connotation is a radical alteration of state, although Shakespeare was of course using it in a punning sense.

It does seem to be popping up quite a lot recently, doesn't it? I guess these phrases get bandied about on the media until they become so hackneyed as to be counterproductive.