Python performance without Blender operators
I'm not sure, but I think it's mainly Blender having to deal with more and more meshes. In your case an extra slowdown is introduced by first creating a "tmp" mesh.

Here you have an improved version of your code, which is a little bit faster, but still slows down after duplicating more objects.

import bpy
from datetime import datetime


def duplicate_object(scene, name, copyOb, iter):
    startTime = datetime.now()

    mesh = copyOb.data.copy()
    mesh.name = name
    ob_new = bpy.data.objects.new(name, mesh)

    scene.objects.link(ob_new)

    print(iter, datetime.now() - startTime)

    return ob_new

for i in range(5000):
    duplicate_object(bpy.context.scene, "toto", bpy.data.objects['Cube'], i)