1620s, vorloffe, from Dutch verlof, literally "permission," from Middle Dutch ver- "completely, for" + laf, lof "permission," which is related to the second element in believe and to leave (n.).
The -gh spelling developed by 1770s and represents an "f" that was once pronounced at the end of the word but disappeared fairly soon thereafter in English.
1783, from furlough (n.). Related: Furloughed; furloughing.