Currently the function slime-repl-merge-histories appears to be buggy in not deleting duplicates, and maintaining order. For example:
i've got a local change for slime-repl-merge-histories that also uses a hashtable to considerably speed up the merging (used by a new slime-repl-delete-history). i'll look into mergin back that change to cvs later today.