This use of bloody came from the practice of oath-making, as in upon God's oath!, thus upon God's bloody oath! (blood making any oath more profound).
Upon God's oath! probably became softened to euphemisms such as gosh, golly etc.; upon God's bloody oath! eventually became bloody oath!
See also absobloodylutely