There actually is a fairly easy way to do this in bulk, but it involves writing some SQL:
UPDATE
UrlRecord SET Slug = categoryUrl.Slug + '/' + u.Slug
FROM [SmartStore].[dbo].[Product] p
inner join [SmartStore].[dbo].Product_Category_Mapping pcm ON pcm.ProductId = p.Id
inner join [SmartStore].[dbo].Category c on c.Id = pcm.CategoryId
inner join UrlRecord u on u.EntityId = p.Id AND u.EntityName = 'Product'
inner join UrlRecord categoryUrl on categoryUrl.EntityId = c.Id AND u.EntityName = 'Category'
(I don't have a DB to test this on at the moment so there may be bugs with the above SQL). Run it in a transaction (with rollback), and a "select * from UrlRecord" before and after, to see the results.
Hope this helps you see what I mean.