Old English fullfyllan "fill up" (a room, a ship, etc.), "make full; take the place of (something)," from full (adj.), here perhaps with a sense of "completion" + fyllan (see fill (v.), which is ultimately from the same root).
It was used from mid-13c. in reference to prophecy (probably translating Latin implere, adimplere). From mid-13c. as "do, perform; carry out, consummate, carry into effect;" from c. 1300 as "complete, finish; satiate, satisfy, gratify." Related: Fulfilled; fulfilling.
Modern English combinations with full tend to have it at the end of the word (as -ful), but this is a recent development and in Old English it was more common at the start, but this word and fulsome appear to be the only survivors.
Self-fulfilling prophecy is attested by 1949, associated with and popularized by U.S. sociologist Robert K. Merton, in writings on racial prejudices, who described it as a false definition of a situation at the outset that evokes a behavior which seems to validate the false concept.