You're right. According to Cecil Adams, it's a Latin legal phrase: see <A HREF="http://www.straightdope.com/classics/a1_139.html" target="_new">http://www.straightdope.com/classics/a1_139.html</A>. It seems more like French phrase. Our <i>felon</i> is probably of Germanic origin, via Anglo-Norman.
Yup, just looked <i>felo-de-se</i> up in the OED. It's described as Anglo-Latin.