We derive new formulas for self-convolutions of Fibonacci numbers of arbitrary order using a combinatorial approach based on counting walks in tiled rectangles. This approach leads to a difference equation whose solution can be expressed in terms of weighted sums involving higher-order Fibonacci numbers, and we evaluate these sums via summation by parts. In addition, we provide combinatorial proofs of further convolution identities for Fibonacci numbers.