The two seem to have pretty different meanings, one meaning a mistake and the other meaning an order. The usual "be- as transitive marker" explanation doesn't really seem to help here either. What could be going on?
befehlen is derived from Old High German bifelahan (to entrust, to bury).
fehlen is derived from Middle High German vælen (to miss, to fail), which is a loanword from Old French falir (to miss, to fail, to be amiss).
They only look similar because of phonetic developments and standardization of German.