A "fee" is from latin "feodum" and olde english "feod" and is linked to latin "fundum" meaning "funds", "bottom", or "estate". Compare it with "legal status", "grounds for a lawsuit", and "legal standing". Funds are debts charged against the estate of a bank (including bank notes such as paper currency), particularly those that can be subdivided and transferred in parcels and annexed (joined) to form other funds.
A "charge" on a person is etymologically as if the person is in the harness pulling a chariot or rickshaw, from Latin "carrus" meaning wagon. A charge of debt may be applied, posted, and offset with one account (of debt) or another pursuant to an account agreement.
Using "charge a fee" instead of simply "charge" would be appropriate in any context where one might have been charged with something other than payment of funds, such as hard labor, specific performance of a contract, or jailtime. The usage in a personal or business letter is usually poor writing style because of unnecessary specificity, but it isn't unreasonable at all in informal speaking or educational and technical documents.