I can work on this while I wait for the theming stuff to get reviewed.

Should I fade out the old button and then fade in the new one?

Yeah, I'd vote for that rather than doing a cross fade. Unlike the top toolbar where the whole toolbar transitions, we are only doing a couple of icons, so completely fading one out before the other fades in makes sense to me.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/25dfa3fb8a3210bc88a69e20b3be6245cadd574b

commit 25dfa3fb8a3210bc88a69e20b3be6245cadd574b
Author: Pedro Amaral <amaralp@chromium.org>
Date: Thu Aug 23 01:25:37 2018

Adding fade animation to bottom toolbar buttons

This CL fades out the old button completely and then fades in the new
button.

Bug:  874097 
Change-Id: I131c2383d645ead9909ca4f4270c855595a25b60
Reviewed-on: https://chromium-review.googlesource.com/1175207
Reviewed-by: Matthew Jones <mdjones@chromium.org>
Reviewed-by: Ted Choc <tedchoc@chromium.org>
Commit-Queue: Pedro Amaral <amaralp@chromium.org>
Cr-Commit-Position: refs/heads/master@{#585353}
[modify] https://crrev.com/25dfa3fb8a3210bc88a69e20b3be6245cadd574b/chrome/android/java/src/org/chromium/chrome/browser/toolbar/BottomToolbarViewBinder.java
[modify] https://crrev.com/25dfa3fb8a3210bc88a69e20b3be6245cadd574b/chrome/android/java/src/org/chromium/chrome/browser/toolbar/ToolbarButtonSlotData.java