Try using pl/sql collections with bulk collect and forall. You may want to break up the update statements into chunks based on the criteria.