Hi,
I've juste created an extension which allow to translate the slug of a post (not a page at this moment). It require WP_Multilingual.
You can download it at this address: http://projects.maleo.net/wp-multilingual-extended/
It adds a "Permalinks" box in the edit box of a post, with one input by WP_Multilingual declared language. During saving, it creates a post meta name "post_slug_{language}" (ex: "post_slug_fr"). It take the title of the post by default (or the titles of each language by default).
In the front site, it take the "post_name" of each post to replace it by the "post_slug_{language}" of the current language.
The only "oooops" for this plugin is that we need to modify the "get_post" function of the core of WP located in the file "/wp-includes/post.php": we need to add the line: apply_filters('get_the_post', $_post); just after: $_post = sanitize_post($_post, $filter); I don't find any existing hook for the purpose of this plugin.
For this version of the plugin, there is no check of a possible duplicated slug, no possilibity to translate pages slugs. It's first a proof of concept and, I hope so, a piece of code you could implement in your plugin.
Cheers,
David