There are various dmenu add-ons that will sort the list by most-frequently-used first:

• history patch
• yeganesh
• pydmenu.py
• Bash script