The bug
The experience level cost to rename an item in an anvil scales with the enchantments and/or repairs on an item. More specifically, the cost to rename an item follows the function 2^n where n is the number of enchantments or repairs done to the item.
This results in weapons and tools having their renaming costs increasing as more repairs and enchantments are added to it. Eventually this cost will top out at 39 levels just to rename a single item.
Renaming an item costs only 1 level when you rename it and also enchant/repair it. Therefore, it is a bug that only renaming the item after enchanting/repairing it costs more than 1 level.
How to reproduce
Enchant an item in an anvil
Put the item in the anvil and give it a new name
Observe that the renaming cost is now greater than 1 experience level and is based upon the number of enchantments put upon the item
This effectively punishes the player for obtaining good enchantments, then renaming the item later. The rename should always cost 1 level regardless of whether a enchantment (or repair) has been added or not.
Image explanations
The first image shows that renaming an unenchanted item costs 1 level.
The second images shows the cost of the sword when you only enchant it (21 levels)
The third images shows the cost of the Sword when adding the enchantment(21 levels) and the enchantment (1 level) for a total of 22 levels of cost.
The fourth images shows the bug. If you rename an item with enchantments already on it while not enchanting/repairing the item at the same time, you will be charged more levels (in this case 16) to rename the item instead of just 1 level like the previous images.
Linked issues
is duplicated by 7
MC-164283
Naming Tools takes too much experience if they have enchantments
Resolved
MC-169480
Name enchanted items
Resolved
MC-171642
Renaming an item after enchanting it
Resolved
MC-176834
Naming Item at Anvil causes loss of almost all levels instead of just 1 level
Resolved
MC-184345
Previously enchanted items cost more experience to rename.
Resolved
relates to 4
MC-45300
Naming an item no longer removes the penalty to repair it / Repair cost level is doubled after each use
Resolved
MCPE-79474
Naming high level enchanted items costs lots of xp
Reopened
MC-780
Anvil: Pricing for renaming weapons (e.g. a sword) is too expensive
Resolved
MC-13246
On certain enchanted items, the Anvil will display a "too expensive" message before attempting to repair, combine, or rename them
Resolved
Still an issue in 1.13 pre-release 1.